记录编号	411200	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.235 s
提交时间	2017-06-04 11:06:58	内存使用	12.54 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 2e5+10;
const int MAXW = 2e6+5;
const int MAXQ = 1e4+10;
struct que{
  int x, y, val;
  int type, ansid, sig;
  bool operator<(const que &q)const{
    return x < q.x;
  }
}qs[MAXN];
int bits[MAXW];
int W;
void add(int x, int d){
  for(; x <= W; x += x&-x)bits[x] += d;
}
int query(int x){
  int s = 0;
  for(; x; x -= x&-x)s += bits[x];
  return s;
}
int ans[MAXQ];
void CDQ(int l, int r){
  if(l == r)return;
  int m = (l+r)>>1;
  CDQ(l, m); CDQ(m+1, r);
  sort(qs+l, qs+m+1); sort(qs+m+1, qs+r+1);
  int j = l;
  for(int i = m+1; i <= r; i++){
    while(j <= m && qs[j].x <= qs[i].x){
      if(qs[j].type)add(qs[j].y, qs[j].val);
      j++;
    }
    if(!qs[i].type)ans[qs[i].ansid] += qs[i].sig*query(qs[i].y);
  }
  for(int i = l; i < j; i++)if(qs[i].type)add(qs[i].y, -qs[i].val);
}
int main(){
  freopen("mokia.in", "r", stdin);
  freopen("mokia.out", "w", stdout);
  int t;
  int totq = 0, tota = 0;  
  while(scanf("%d", &t) && t != 3){
    int x, y, z, w, v;
    switch(t){
      case 0: scanf("%d", &W);
      break;
      case 1:
        scanf("%d %d %d", &x, &y, &v);
        qs[++totq] = (que){x, y, v, 1, 0, 0};
      break;
      case 2:
        scanf("%d %d %d %d", &x, &y, &z, &w);
        qs[++totq] = (que){z, w, 0, 0, ++tota, 1};
        qs[++totq] = (que){x-1, y-1, 0, 0, tota, 1};
        qs[++totq] = (que){x-1, w, 0, 0, tota, -1};
        qs[++totq] = (que){z, y-1, 0, 0, tota, -1};
      break;
    }
  }
  CDQ(1, totq);
  for(int i = 1; i <= tota; i++)printf("%d\n", ans[i]);
  return 0;
}