ulvis.paste.net

Paste Search Dynamic
Recent pastes
buildAux
  1. #include <bits/stdc++.h>
  2. #define TAM 1024
  3. using namespace std;
  4. int seg[4*TAM][4*TAM], segAux[4*TAM], tam;
  5. int buildAux(int start, int end, int node){
  6.     if(start==end){
  7.         segAux[node]=0;
  8.         return node;
  9.     }
  10.     int mid=(start+end)/2;
  11.     return max(buildAux(start,mid,2*node),buildAux(mid+1,end,2*node+1));
  12. }
  13. void build(int start, int end, int node){
  14.     if(start==end){
  15.         for(int i=1;i<=tam;i++)
  16.             seg[node][i]=segAux[i];
  17.         return;
  18.     }
  19.     int mid=(start+end)/2;
  20.     build(start,mid,2*node);
  21.     build(mid+1, end, 2*node+1);
  22.     for(int i=1;i<=tam;i++)
  23.         seg[node][i]=seg[2*node][i]+seg[2*node+1][i];
  24.     return;
  25.  
  26. }
  27. int query_aux(int pos, int start, int end, int x1,int x2,int node){
  28.     if(x1>end || x2<start)
  29.         return 0;
  30.     if(x1<=start&&x2>=end)
  31.         return seg[node][pos];
  32.     int mid=(start+end)/2;
  33.     int p1 = query_aux(2*pos,start,mid,x1,x2,node);
  34.     int p2 = query_aux(2*pos+1,mid+1,end,x1,x2,node);
  35.     return p1+p2;
  36. }
  37. int query(int pos, int start_x, int end_x, int start_y,int end_y, int x1, int x2, int y1, int y2){
  38.     if(y1>end_y||y2<start_y)  
  39.         return 0;
  40.     if(y1<=start_y&&y2>=end_y)
  41.  
  42.         return query_aux(1,start_x,end_x,x1,x2,pos);
  43.     int mid=(start_y+end_y)/2;
  44.     int p1 = query(2*pos, start_x, end_x, start_y, mid, x1, x2, y1, y2);
  45.     int p2 = query(2*pos+1,start_x, end_x,mid+1, end_y, x1, x2, y1, y2);
  46.     return p1+p2;
  47. }
  48.  
  49. void update_aux(int pos, int start, int end, int x, int valor, int node){
  50.     if(start==end){
  51.         seg[node][pos]+=valor;
  52.         return;
  53.     }
  54.     int mid=(start+end)/2;
  55.     if(x>=start&&x<=mid)
  56.         update_aux(2*pos,start, mid, x, valor, node);
  57.     else
  58.         update_aux(2*pos+1, mid+1, end, x, valor, node);
  59.     seg[node][pos]=seg[node][2*pos]+seg[node][2*pos+1];
  60. }
  61.  
  62. void update(int pos, int start_x, int end_x, int start_y, int end_y, int x, int y, int valor){
  63.     if(start_y==end_y){
  64.         update_aux(1,start_x, end_x, x, valor, pos);
  65.         return;
  66.     }
  67.     int mid=(start_y+end_y)/2;
  68.     if(y>=start_y&&y<=mid)
  69.         update(2*pos, start_x, end_x, start_y, mid, x, y, valor);
  70.     else
  71.         update(2*pos+1, start_x, end_x, mid+1, end_y, x, y, valor);
  72.     for(int i=1;i<=tam;i++)
  73.         seg[pos][i]=seg[2*pos][i]+seg[2*pos+1][i];
  74.    
  75. }
  76.  
  77. int main() {
  78.   int x,y,p,q,x1,x2,y1,y2,v;
  79.   char op;
  80.   while(scanf("%d%d%d",&x,&y,&p)&&(x||y||p)){
  81.     tam=buildAux(1,x,1);
  82.     build(1,y,1);
  83.     scanf("%d",&q);
  84.     while(q--){
  85.         //cin>>op;
  86.         scanf(" %c",&op);
  87.         if(op=='A'){
  88.           //cin>>v>>x1>>y1;
  89.           scanf(" %d %d %d",&v,&x1,&y1);
  90.           x1++;y1++;
  91.           update(1,1,x,1,y,x1,y1,v);
  92.         }
  93.         else{
  94.           cin>>x1>>y1>>x2>>y2;
  95.           //scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  96.           x1++;y1++;x2++;y2++;
  97.           if(y2<y1)
  98.             swap(y2,y1);
  99.           if(x2<x1)
  100.             swap(x2,x1);  
  101.           cout<<p*query(1,1,x,1,y,x1,x2,y1,y2)<<"\n";
  102.           //printf("%d\n",p*query(1,1,x,1,y,x1,x2,y1,y2));
  103.         }
  104.     }
  105.     printf("\n");
  106.  
  107.   }
  108.  
  109. }
Parsed in 0.027 seconds