记录编号	154007	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	3.718 s
提交时间	2015-03-20 20:50:54	内存使用	11.80 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============
struct Data{
   int x,y,v,k,type;///x y濞戞挸鎼??妤呭冀閸ラ?绀塿闁?闁?挳寮?敮?绀塳闁??閹煎瓨鏌ㄩ幗銏＄▔閳?绋??闂?缁辨挤ype闁?閹奸攱鎷呭??缂
   Data(int x=0,int y=0,int v=0,int k=0,int type=0):x(x),y(y),v(v),k(k),type(type){}
   bool operator <(const Data &rhs) const{
      return x<rhs.x;
   }
};
///==============var declaration=================
const int MAXN=2000010;
int n,m,tot=0,tail=0;
Data Q[200010];
int ans[10010],Bit[MAXN];
///==============function declaration============
void Add_Opt(int x,int y,int v,int k,int type);
int lowbit(int x){return x&-x;}
int Query(int x){int res=0;while (x>0){res+=Bit[x];x-=lowbit(x);}return res;}
void Add(int x,int v){while (x<=n){Bit[x]+=v;x+=lowbit(x);}}
void CDQ(int l,int r);
///==============main code=======================
int main()
{
//#define FILE__
//#ifdef FILE__
   freopen("mokia.in","r",stdin);
   freopen("mokia.out","w",stdout);
//#endif
   int cmd;
   while (scanf("%d",&cmd)&&cmd!=3){
      if (cmd==0)
         scanf("%d",&n);
      else if (cmd==1){///Insert
         int x,y,A;
         scanf("%d%d%d",&x,&y,&A);
         x++;y++;
         Add_Opt(x,y,A,0,1);///x,y,v,k,type
      }
      else if (cmd==2){
         int x1,x2,y1,y2;
         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);tail++;
         x1++;x2++;y1++;y2++;
         Add_Opt(x2,y2,1,tail,2);
         Add_Opt(x1-1,y1-1,1,tail,2);
         Add_Opt(x1-1,y2,-1,tail,2);
         Add_Opt(x2,y1-1,-1,tail,2);
      }
   }n++;
   CDQ(1,tot);
   for(int i=1;i<=tail;i++)
      printf("%d\n",ans[i]);
   return 0;
}
///================fuction code====================
void Add_Opt(int x,int y,int v,int k,int type){
   Q[++tot]=Data(x,y,v,k,type);
}
void CDQ(int l,int r){
   int m=(l+r)>>1;
   if (l==r)   return ;
   CDQ(l,m);CDQ(m+1,r);
   sort(Q+l,Q+m+1);sort(Q+1+m,Q+r+1);
   int L=l;
   for(int i=m+1;i<=r;i++){
      while (L<=m&&Q[L].x<=Q[i].x){
         if (Q[L].type==1)
            Add(Q[L].y,Q[L].v);
         L++;
      }
      if (Q[i].type==2)
         ans[Q[i].k]+=Q[i].v*Query(Q[i].y);
   }
   for(int i=l;i<L;i++)
      if (Q[i].type==1)
         Add(Q[i].y,-Q[i].v);
}