一维区间修改与查询

题目描述

White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row belongs the a[i][j]-th type.
White Cloud wants to help White Rabbit fertilize plants, but the i-th plant can only adapt to the i-th fertilizer. If the j-th fertilizer is applied to the i-th plant (i!=j), the plant will immediately die.
Now White Cloud plans to apply fertilizers T times. In the i-th plan, White Cloud will use k[i]-th fertilizer to fertilize all the plants in a rectangle [x1[i]...x2[i]][y1[i]...y2[i]].
White rabbits wants to know how many plants would eventually die if they were to be fertilized according to the expected schedule of White Cloud.

输入描述:

The first line of input contains 3 integers n,m,T(n*m<=1000000,T<=1000000)
For the next n lines, each line contains m integers in range[1,n*m] denoting the type of plant in each grid.
For the next T lines, the i-th line contains 5 integers x1,y1,x2,y2,k(1<=x1<=x2<=n,1<=y1<=y2<=m,1<=k<=n*m)

输出描述:

Print an integer, denoting the number of plants which would die.

示例1

输入

复制

输出

复制

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6  
 7 //c[i] = a[i]-a[i-1]
 8 //c2[i] = (i-1)*c[i]
 9 //树状数组维护c,c2
10 //ans[1-n]: n*sigma(c,n) - sigma(c2,n)
11 const int N = 100000010;
12 #define lowbit(i) (i&(-i))
13 LL c[N],c2[N];
14 LL n;
15 void up(LL *r,LL x,LL val){
16     while(x<=n){
17         r[x] += val;
18         x += lowbit(x);
19     }
20 }
21 LL down(LL *r,LL x){
22     LL ans = 0;
23     while(x){
24         ans += r[x];
25         x -= lowbit(x);
26     }
27     return ans;
28 }
29  
30 int main()
31 {
32     LL q;
33     LL a,b,f;
34     scanf("%lld",&n);
35     scanf("%lld",&q);
36     for(int i = 1; i <= n; i++){
37         LL f;
38         scanf("%lld",&f);
39         up(c,i,f); up(c,i+1,-f);
40         up(c2,i,f*(i-1)); up(c2,i+1,-f*(i));
41     }
42  
43     while(q--){
44         int type;
45         scanf("%d",&type);
46  
47         if(type==1){
48             scanf("%lld%lld%lld",&a,&b,&f);
49             up(c,a,-f); up(c,b+1,f);
50             up(c2,a,-f*(a-1)); up(c2,b+1,f*b);
51              
52         }
53         else{
54             scanf("%lld%lld%lld",&a,&b,&f);
55             up(c,a,f); up(c,b+1,-f);
56             up(c2,a,f*(a-1)); up(c2,b+1,-f*b);
57         }
58  
59     }
60     scanf("%lld%lld",&a,&b);
61             LL l = (a-1)*down(c,a-1) - down(c2,a-1);
62             LL r = b*down(c,b) - down(c2,b);
63             printf("%lld
",r-l);
64     return 0;
65 }