题目

 

思路&题解

最开始想的是O(NQ)的差分数组，以为5e8能跑过去，然而。。。。

这道题可以O(Q)做，即用二维差分数组，其实似乎跟二维树状数组差不多，主要这道题是三角形。我们可以选择对角线差分，即·差分后可将其分为两个操作，若现在修改成为了这样的：

差分数组中就可以在最左列加上s，最后一行减去s，而这样的操作是可以进行差分的，于是用前缀数组差分即可

代码

#include<bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 1003; int n , q; ll suml[MAXN][MAXN] , summ[MAXN][MAXN] , sumh[MAXN][MAXN]; ll sump[MAXN][MAXN] , sum[MAXN][MAXN]; int min_( int x , int y ){ if( x <= y ) return x;return y; } int max_( int x , int y ){ if( x <= y ) return y;return x; } inline char GetChar(){ static char buf[10001],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,10001,stdin),p1==p2)?EOF:*p1++; } inline void Read(int &n){ short f=1; long long x=0; char c=GetChar(); while(isdigit(c)==false){ if(c=='-'){ f=-1; } c=GetChar(); } while(isdigit(c)==true){ x=((x<<3)+(x<<1)+(c^48)); c=GetChar(); } n=x*f; } int main(){ scanf( "%d%d" , &n , &q ); while( q -- ){ int r , c , l , s; scanf( "%d%d%d%d" , &r , &c, &l , &s ); suml[r][c] += s; suml[min_(r+l,n+1)][c] -= s; sumh[min_(r+l,n+1)][min_(c+1,n+1)] -= s; sumh[min_(r+l,n+1)][min_(c+l+1,n+1)] += s; } for( int j = 1 ; j <= n ; j ++ ){ for( int i = 1 ; i <= n ; i ++ ){ sump[i][j] = sump[i-1][j] + suml[i][j]; summ[i][j] = sump[i][j]; } } memset( sump , 0 , sizeof( sump ) ); for( int i = 1 ; i <= n ; i ++ ){ for( int j = 1 ; j <= n ; j ++ ){ sump[i][j] = sump[i][j-1] + sumh[i][j]; summ[i][j] += sump[i][j]; } } ll ans = 0; for( int i = 1 ; i <= n ; i ++ ){ for( int j = 1 ; j <= n ; j ++ ){ sum[i][j] = sum[i-1][j-1] + summ[i][j]; ans = ans ^ sum[i][j]; // printf( "%lld " , sum[i][j] ); } // printf( "\n" ); } printf( "%lld\n" , ans ); return 0; }