QWQ cdq+扫描线 WA的死去活来

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
#define mid ((l+r)>>1)
using namespace std;

const int maxn=400086;
const int maxm=maxn<<1;

typedef long long ll;
int yy[maxn],n,m,nn,Top;
ll ans[maxn],sum[maxn];

struct node {
    int x1,y1,x2,y2,ops;
}a[maxn];

struct Node {
    int x,y1,y2,ops,pos;
}tmp[maxn];

inline int Read(){
    int x=0;char c=getchar();
    while (!isdigit(c))c=getchar();
    while (isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x;
} 

inline int cmp(Node x,Node y){return x.x<y.x;}

inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){for (rint i=x;i<=nn;i+=lowbit(i))sum[i]+=y;}
inline ll query(int x){ll ans=0;for (rint i=x;i;i-=lowbit(i))ans+=sum[i];return ans;}

inline void cdq(int l,int r){
    if (l==r)return ;
    cdq(l,mid);cdq(mid+1,r);
    Top=0;
    for (rint i=l;i<=mid;++i){
        if (a[i].ops==2){
            tmp[++Top].ops=2;
            tmp[Top].x=a[i].x1;
            tmp[Top].y1=a[i].y1;
            tmp[Top].y2=a[i].y2;
        }
    }
    for (rint i=mid+1;i<=r;++i){
        if (a[i].ops!=2){
            tmp[++Top].ops=-1;
            tmp[Top].x=a[i].x1-1;
            tmp[Top].y1=a[i].y1;
            tmp[Top].y2=a[i].y2;		
            tmp[Top].pos=i;
            tmp[++Top].ops=1;
            tmp[Top].x=a[i].x2;
            tmp[Top].y1=a[i].y1;
            tmp[Top].y2=a[i].y2;		
            tmp[Top].pos=i;	
        }
    }
    sort(tmp+1,tmp+1+Top,cmp);
    for (rint i=1;i<=Top;++i){
        if (tmp[i].ops==2){
            add(tmp[i].y1,tmp[i].y2);
        }
        else {
            ans[tmp[i].pos]+=(tmp[i].ops*(query(tmp[i].y2)-query(tmp[i].y1-1)));
        }
    }
    for (rint i=1;i<=Top;++i)
        if (tmp[i].ops==2)
            add(tmp[i].y1,-tmp[i].y2);
}

int main(){
    nn=Read(),nn=Read();nn=0;
    while (1){
        int tadyz_xz_sm=Read();
        if (tadyz_xz_sm==3)break;
        if (tadyz_xz_sm==2){
            a[++n].x1=Read(),a[n].y1=Read(),a[n].x2=Read(),a[n].y2=Read(),a[n].ops=1;
            yy[++nn]=a[n].y1,yy[++nn]=a[n].y2;
        }
        else {
            a[++n].x1=Read(),a[n].y1=Read(),a[n].y2=Read(),a[n].ops=2;yy[++nn]=a[n].y1;
        }
    }
    
    sort(yy+1,yy+1+nn);
    nn=unique(yy+1,yy+1+nn)-yy-1;
    
    for (rint i=1;i<=n;++i){
        a[i].y1=lower_bound(yy+1,yy+1+nn,a[i].y1)-yy;
        if (a[i].ops!=2){
            a[i].y2=lower_bound(yy+1,yy+1+nn,a[i].y2)-yy;		
        }
    }
    
    cdq(1,n);
    
    for (rint i=1;i<=n;++i){
        if (a[i].ops!=2)printf("%lld\n",ans[i]);
    }
    return 0;
}