BOI2007 Mokia-白红宇

BOI2007 Mokia

阅读量：5312 次

发布时间：2019-06-14

本文共 2618 字，大约阅读时间需要 8 分钟。

这个题其实和板子题差不多……不过这次修改和询问是分离开的，然后一个询问要被拆分成4个，就是维护二维前缀和的方式。

我的做法比较奇怪……（怎么我\(CDQ\)分治的题做法都很奇怪），别人都是按时间排序然后归并x，树状数组统计y，用x作为限制，因为这样时间天然有序。我是按x排序然后归并时间……其实这样也能做，但是一来比较慢（一开始要\(sort\)），二来我非常智障的把每个询问的时间没有搞成同一个值……

之后套板子做就可以了。

// luogu-judger-enable-o2#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')#define fr friend inline#define y1 poj#define mp make_pair#define pr pair
             
              #define fi first#define sc second#define pb push_back#define lowbit(x) x & (-x)#define B printf("Bug\n");using namespace std;typedef long long ll;const int M = 400005;const int N = 2000005;const double INF = 1e15;const double eps = 1e-7;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}struct node{ int x,y,tim,val; bool opa; bool operator < (const node &g)const { if(x == g.x && tim == g.tim) return y < g.y; if(x == g.x) return tim < g.tim; return x < g.x; }}a[M];int n,cnt,x1,y1,x2,y2,A,op,ans[N],Ti;bool vis[N];struct treearray{ int c[N]; void add(int x,int v) {while(x <= N-2) c[x] += v,x += lowbit(x);} int ask(int x) {int cur = 0;while(x) cur += c[x],x -= lowbit(x); return cur;}}T;bool cmp(const node &p,const node &q){ if(p.tim == q.tim) return p.y < q.y; return p.tim < q.tim;} void CDQ(const int &l,const int &r){ if(l == r) return; int mid = (l+r) >> 1; CDQ(l,mid),CDQ(mid+1,r); sort(a+l,a+mid+1,cmp),sort(a+mid+1,a+r+1,cmp); int j = l; rep(i,mid+1,r) { if(a[i].opa) continue; while(j <= mid && a[j].tim < a[i].tim) { if(!a[j].opa) {j++;continue;} T.add(a[j].y,a[j].val),j++; } ans[a[i].tim] += a[i].val * T.ask(a[i].y); } rep(i,l,j-1) if(a[i].opa) T.add(a[i].y,-a[i].val);}int main(){ n = read(),n = read(); while(scanf("%d",&op) && op != 3) { Ti++; if(op == 1) a[++cnt].x = read(),a[cnt].y = read(),a[cnt].val = read(),a[cnt].opa = 1,a[cnt].tim = Ti; else { x1 = read(),y1 = read(),x2 = read(),y2 = read(),vis[Ti] = 1; a[++cnt].x = x1-1,a[cnt].y = y1-1,a[cnt].val = 1,a[cnt].tim = Ti; a[++cnt].x = x1-1,a[cnt].y = y2,a[cnt].val = -1,a[cnt].tim = Ti; a[++cnt].x = x2,a[cnt].y = y1-1,a[cnt].val = -1,a[cnt].tim = Ti; a[++cnt].x = x2,a[cnt].y = y2,a[cnt].val = 1,a[cnt].tim = Ti; } } sort(a+1,a+1+cnt); CDQ(1,cnt); rep(i,1,Ti) if(vis[i]) printf("%d\n",ans[i]); return 0;}

转载于:https://www.cnblogs.com/captain1/p/10089005.html

你可能感兴趣的文章