深圳做微信网站公司,c 做网站设计,哪个网站可以做字体,潜江网站开发BZOJ #2874. 训练士兵descriptionsolutioncodedescription
Ryz正在着手于训练一批精锐士兵
Ryz手下有n*m个士兵#xff0c;排成一个n行m列的方阵。在一天中#xff0c;ryz会对士兵下达一些命令#xff0c;每个命令作用于一个小方阵的所有士兵#xff0c;并且会增加他们的…
BZOJ #2874. 训练士兵descriptionsolutioncodedescription
Ryz正在着手于训练一批精锐士兵
Ryz手下有n*m个士兵排成一个n行m列的方阵。在一天中ryz会对士兵下达一些命令每个命令作用于一个小方阵的所有士兵并且会增加他们的疲劳值。现在ryz想知道在一整天训练中某些小方阵中的士兵的疲劳值总和是多少
Input
第一行有3个整数n,m,k,q。分别表示方阵的行数、列数、指令数和询问数。
接下来k行每行5个整数x1,x2,y1,y2,s描述一个指令表示这条指令对所有坐标(x,y)满足x1xx2且y1yy2的士兵产生了s的疲劳值。
(1x1x2n1y1y2m0s1000)
接下来q行每行2个整数x,y(x,y10^9)描述一个询问询问是被加密的。一个询问的密码是上一个询问的答案(记为c)第一个询问的密码是0。询问参数的计算方式如下
x1c % n1,x2(cx) % n1如果x1x2则交换x1和x2
y1c % m1,y2(cy) % m 1如果y1y2则交换y1和y2
询问所有坐标(x,y)满足x1xx2且y1yy2的士兵的疲劳值总和。
保证答案2^64
Output
对于每个询问输出一行答案
Sample 输入样例1
4 5 3 3
1 3 2 2 7
2 4 2 3 5
1 4 4 5 6
1 2
0 3
2 2输出样例1
24
12
46第一次询问的是左上角坐标为(1,1),右下角坐标为(2,3)的这个矩形
第二次询问的是左上角坐标为(1,3),右下角坐标为(1,5)的这个矩形
第三次询问的是左上角坐标为(1,3)右下角坐标为(3,5)这个矩形
输入样例2
5 5 5 5
1 1 1 3 242
1 4 4 5 83
3 5 3 3 221
2 2 1 3 254
5 5 2 2 105
0 1
0 4
2 1
1 3
0 1输出样例2
484
0
992
442
304Hint
对于100%的数据 n,m10^8,k40000,q100000
solution
一个二维矩阵一般处理套路就是二维差分
对于修改维护(x,y)(x,y)(x,y)到右下角的贡献
即(x1,y1,x2,y2)(x_1,y_1,x_2,y_2)(x1,y1,x2,y2)差分成(x1,y1)−(x1,y21)−(x21,y1)(x21,y21)(x_1,y_1)-(x_1,y_21)-(x_21,y_1)(x_21,y_21)(x1,y1)−(x1,y21)−(x21,y1)(x21,y21)
只用修改四个点
对于询问则求(x,y)(x,y)(x,y)到左上角的贡献
即(x1,y1,x2,y2)(x_1,y_1,x_2,y_2)(x1,y1,x2,y2)差分成(x2,y2)−(x1,y2−1)−(x2−1,y1)(x1−1,y1−1)(x_2,y_2)-(x_1,y_2-1)-(x_2-1,y_1)(x_1-1,y_1-1)(x2,y2)−(x1,y2−1)−(x2−1,y1)(x1−1,y1−1)
只用查询四个点
考虑差分后的某个修改点(i,j)(i,j)(i,j)对于差分后的某个查询点(x,y)(x,y)(x,y)的实际影响
显然∀row∈[i,x],col∈[j,y]\forall_{row\in[i,x],col\in[j,y]}∀row∈[i,x],col∈[j,y]的点对(row,col)(row,col)(row,col)都会加上si,js_{i,j}si,j带来的劳累贡献和即(x−i1)(y−j1)si,j(x-i1)(y-j1)s_{i,j}(x−i1)(y−j1)si,j
那么查询一个左上角的(1,1)−(x,y)(1,1)-(x,y)(1,1)−(x,y)矩阵这里面每个修改点的劳累贡献都可以计算求和就是这个查询矩阵的答案 ∑i1x∑j1y(x−i1)(y−j1)si,j\sum_{i1}^x\sum_{j1}^y(x-i1)(y-j1)s_{i,j} i1∑xj1∑y(x−i1)(y−j1)si,j
∑i1x∑j1y(xyyx1−iy−i−jx−jij)si,j\sum_{i1}^x\sum_{j1}^y(xyyx1-iy-i-jx-jij)s_{i,j} i1∑xj1∑y(xyyx1−iy−i−jx−jij)si,j
∑i1x∑j1y((x1)(y1)−(y1)i−(x1)jij)si,j\sum_{i1}^x\sum_{j1}^y\Big((x1)(y1)-(y1)i-(x1)jij\Big)s_{i,j} i1∑xj1∑y((x1)(y1)−(y1)i−(x1)jij)si,j
(x1)(y1)∑i1x∑j1xsi,j−(y1)∑i1x∑j1xsi,j∗i−(x1)∑i1x∑j1xsi,j∗j∑i1x∑j1xsi,j∗i∗j(x1)(y1)\sum_{i1}^x\sum_{j1}^xs_{i,j}-(y1)\sum_{i1}^x\sum_{j1}^xs_{i,j}*i-(x1)\sum_{i1}^x\sum_{j1}^xs_{i,j}*j\sum_{i1}^x\sum_{j1}^xs_{i,j}*i*j (x1)(y1)i1∑xj1∑xsi,j−(y1)i1∑xj1∑xsi,j∗i−(x1)i1∑xj1∑xsi,j∗ji1∑xj1∑xsi,j∗i∗j
对修改的(i,j,si,j)(i,j,s_{i,j})(i,j,si,j)分别维护四个值即可
剩下的就是二维主席树了将二维坐标离散化即可
code
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;
#define int long long
#define maxn 200000
vector pair int, int G[maxn];
struct node { int lson, rson, o, i, j, ij;node(){}node( int x, int y, int w ) {o w, i x * w, j y * w, ij x * y * w;}void operator ( node New ) {o New.o, i New.i, j New.j, ij New.ij;}
}t[maxn * 30];
struct Node { int x, y, w; }opt[maxn];
int n, m, k, Q, tot, cnt, cnt_x, cnt_y;
int root[maxn], X[maxn], Y[maxn];void modify( int now, int lst, int l, int r, int pos, node New ) {t[now cnt] t[lst];t[now] New;if( l r ) return;int mid ( l r ) 1;if( pos mid ) modify( t[now].lson, t[lst].lson, l, mid, pos, New );else modify( t[now].rson, t[lst].rson, mid 1, r, pos, New );
}int query_o( int now, int l, int r, int pos ) {if( ! now or pos l ) return 0;if( r pos ) return t[now].o;int mid ( l r ) 1;return query_o( t[now].lson, l, mid, pos ) query_o( t[now].rson, mid 1, r, pos );
}int query_i( int now, int l, int r, int pos ) {if( ! now or pos l ) return 0;if( r pos ) return t[now].i;int mid ( l r ) 1;return query_i( t[now].lson, l, mid, pos ) query_i( t[now].rson, mid 1, r, pos );
}int query_j( int now, int l, int r, int pos ) {if( ! now or pos l ) return 0;if( r pos ) return t[now].j;int mid ( l r ) 1;return query_j( t[now].lson, l, mid, pos ) query_j( t[now].rson, mid 1, r, pos );
}int query_ij( int now, int l, int r, int pos ) {if( ! now or pos l ) return 0;if( r pos ) return t[now].ij;int mid ( l r ) 1;return query_ij( t[now].lson, l, mid, pos ) query_ij( t[now].rson, mid 1, r, pos );
}int query( int x, int y ) {if( ! x or ! y ) return 0;int i upper_bound( X 1, X cnt_x 1, x ) - X - 1;int j upper_bound( Y 1, Y cnt_y 1, y ) - Y - 1;int s1 ( x 1 ) * ( y 1 ) * query_o( root[i], 1, cnt_y, j );int s2 ( y 1 ) * query_i( root[i], 1, cnt_y, j );int s3 ( x 1 ) * query_j( root[i], 1, cnt_y, j );int s4 query_ij( root[i], 1, cnt_y, j );return s1 - s2 - s3 s4;
}signed main() {scanf( %lld %lld %lld %lld, n, m, k, Q );for( int i 1, x1, x2, y1, y2, s;i k;i ) {scanf( %lld %lld %lld %lld %lld, x1, x2, y1, y2, s );opt[ tot] { x1, y1, s };opt[ tot] { x1, y2 1, -s };opt[ tot] { x2 1, y1, -s };opt[ tot] { x2 1, y2 1, s };X[ cnt_x] x1, X[ cnt_x] x2 1;Y[ cnt_y] y1, Y[ cnt_y] y2 1;}sort( X 1, X cnt_x 1 );cnt_x unique( X 1, X cnt_x 1 ) - X - 1;sort( Y 1, Y cnt_y 1 );cnt_y unique( Y 1, Y cnt_y 1 ) - Y - 1;for( int i 1;i tot;i ) {int x lower_bound( X 1, X cnt_x 1, opt[i].x ) - X;int y lower_bound( Y 1, Y cnt_y 1, opt[i].y ) - Y;G[x].push_back( make_pair( y, i ) );}for( int i 1;i cnt_x;i ) {root[i] root[i - 1];for( auto E : G[i] ) {int j E.first, id E.second;modify( root[i], root[i], 1, cnt_y, j, node( opt[id].x, opt[id].y, opt[id].w ) );}}int ans 0, x1, y1, x2, y2, x, y;while( Q -- ) {scanf( %lld %lld, x, y );x1 ans % n 1, x2 ( ans x ) % n 1;if( x1 x2 ) swap( x1, x2 );y1 ans % m 1, y2 ( ans y ) % m 1;if( y1 y2 ) swap( y1, y2 );printf( %lld\n, ans query( x2, y2 ) - query( x2, y1 - 1 ) - query( x1 - 1, y2 ) query( x1 - 1, y1 - 1 ) );}return 0;
}
