样例没过,玄关求条
查看原帖
样例没过,玄关求条
1211899
Bobi2014楼主2025/7/3 18:03
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5,M = 2e5 + 5;
struct node{
    int x,y,ti,pos,val,opt;
} e[M],t[M];
int n,maxx,ans[10005],opt,ti,qcnt;
namespace SegmentTree{
    int cnt[N << 2];
    void update(int p,int pos,int val,int l = 1,int r = maxx){
        if(l == r){
            cnt[p] += val;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid){
            update(p << 1,pos,val,l,mid);
        }else{
            update(p << 1 | 1,pos,val,mid + 1,r);
        }
        cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
    }
    int query(int p,int ql,int qr,int l = 1,int r = maxx){
        if(ql <= l and r <= qr){
            return cnt[p];
        }
        int mid = (l + r) >> 1,ans = 0;
        if(ql <= mid){
            ans += query(p << 1,ql,qr,l,mid);
        }
        if(qr > mid){
            ans += query(p << 1 | 1,ql,qr,mid + 1,r);
        }
        return ans;
    }
}
bool cmp(node a,node b){
    if(a.ti != b.ti){
        return a.ti < b.ti;
    }
    if(a.x != b.x){
        return a.x < b.x;
    }
    if(a.y != b.y){
        return a.y < b.y;
    }
    return a.val > b.val;
}
void cdq(int l,int r){
    if(l == r){
        return;
    }
    int mid = (l + r) >> 1;
    cdq(l,mid);
    cdq(mid + 1,r);
    int cnt = 0,p = l,q = mid + 1;
    while(p <= mid and q <= r){
        if(e[p].x <= e[q].x){
            if(e[p].opt == 0){
                SegmentTree::update(1,e[p].y,e[p].val);
            }
            t[cnt++] = e[p ++];
        }else{
            if(e[q].opt != 0){
                ans[e[q].pos] += SegmentTree::query(1,1,e[q].y) * e[q].opt;
            }
            t[cnt++] = e[q ++];
        }
    }
    while(p <= mid){
        if(e[p].opt == 0){
            SegmentTree::update(1,e[p].y,e[p].val);
        }
        t[cnt++] = e[p ++];
    }
    while(q <= r){
        if(e[q].opt != 0){
            ans[e[q].pos] += SegmentTree::query(1,1,e[q].y) * e[q].opt;
        }
        t[cnt++] = e[q ++];
    }
    for(int i = l;i <= mid;i ++){
        if(e[i].opt == 0){
            SegmentTree::update(1,e[i].y,-e[i].val);
        }
    }
    for(int i = l;i <= r;i ++){
        e[i] = t[i - l + 1];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> opt >> maxx;
    maxx += 1;
    while(true){
        cin >> opt;
        if(opt == 3){
            break;
        }
        if(opt == 1){
            int x,y,val;
            cin >> x >> y >> val;
            x ++,y ++;
            x = maxx - x + 1;
            e[++n] = {x,y,++ti,0,val,0};
        }else{
            int ax,bx,ay,by;
            cin >> bx >> ay >> ax >> by;
            ax ++,bx ++,ay ++,by ++;
            ax = maxx - ax + 1;
            bx = maxx - bx + 1;
            e[++n] = {bx,by,++ti,++qcnt,0,1};
            e[++n] = {ax - 1,ay - 1,ti,qcnt,0,1};
            e[++n] = {ax - 1,by,ti,qcnt,0,-1};
            e[++n] = {bx,ay - 1,ti,qcnt,0,-1};
        }
    }
    sort(e + 1,e + n + 1,cmp);
    cdq(1,n);
    for(int i = 1;i <= qcnt;i ++){
        cout << ans[i] << "\n";
    }
    return 0;
}
2025/7/3 18:03
加载中...