1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pf printf 4 #define mem(a,b) memset(a,b,sizeof(a)) 5 #define scand(x) scanf("%llf",&x) 6 #define f(i,a,b) for(int i=a;i<=b;i++) 7 #define scan(a) scanf("%d",&a) 8 #define dbg(args) cout<<#args<<":"<<args<<endl; 9 #define pb(i) push_back(i) 10 #define ppb(x) pop_back(x) 11 #define inf 0x3f3f3f3f 12 #define maxn 1010 13 #define ll long long 14 int n,m,t; 15 ll c[maxn<<1][maxn<<1]; 16 int lowbit(int x){ 17 return x&(-x); 18 } 19 void update(int x,int y,ll C){ 20 while(x<maxn){ 21 int tmp=y; 22 while(tmp<maxn){ 23 c[x][tmp]+=C; 24 tmp+=lowbit(tmp); 25 } 26 x+=lowbit(x); 27 } 28 } 29 ll query(int x,int y){ 30 ll ans=0; 31 while(x>0){ 32 int tmp=y; 33 while(tmp>0){ 34 ans+=c[x][tmp]; 35 tmp-=lowbit(tmp); 36 } 37 x-=lowbit(x); 38 } 39 return ans; 40 } 41 ll query2(int l1,int r1,int l2,int r2){ 42 return query(l2,r2)-query(l1-1,r2)-query(l2,r1-1)+query(l1-1,r1-1); 43 } 44 45 int main(){ 46 ios::sync_with_stdio(false); 47 scan(t); 48 f(kk,1,t){ 49 f(i,1,1001){ 50 f(j,1,1001){ 51 c[i][j]=lowbit(i)*lowbit(j);//设置原数组每一个元素都是1，用update(i,j,1)用O(n*log(n)^2)时间会超时 52 } 53 } 54 scan(n); 55 //cout<<"n is: "<<n<<endl; 56 int xa,xb,ya,yb; 57 ll n1; 58 pf("Case %d: ",kk); 59 while(n--){ 60 char s; 61 getchar(); 62 scanf("%c",&s); 63 //cout<<"s is: "<<s<<endl; 64 if(s=='S'){ 65 scanf("%d%d%d%d",&xa,&ya,&xb,&yb); 66 xa++,xb++,ya++,yb++; 67 if(xa>xb) swap(xa,xb); 68 if(ya>yb) swap(ya,yb); 69 pf("%lld ",query2(xa,ya,xb,yb)); 70 //cout<<"query successful! "; 71 } 72 else if(s=='A'){ 73 scanf("%d%d%lld",&xa,&ya,&n1); 74 update(xa+1,ya+1,n1); 75 //cout<<"update point successful! "; 76 } 77 else if(s=='D'){ 78 scanf("%d%d%lld",&xa,&ya,&n1); 79 xa++,ya++; 80 ll tmp=query2(xa,ya,xa,ya); 81 n1=min(n1,tmp); 82 update(xa,ya,-n1); 83 } 84 else if(s=='M'){ 85 scanf("%d%d%d%d%lld",&xa,&ya,&xb,&yb,&n1); 86 xa++,ya++,xb++,yb++; 87 ll tmp=query2(xa,ya,xa,ya); 88 n1=min(n1,tmp); 89 update(xa,ya,-n1); 90 update(xb,yb,n1); 91 } 92 //cout<<"now n is: "<<n<<endl; 93 } 94 } 95 }
HDU1892，长见识了。