P4390 [BalkanOI 2007] Mokia 摩基亚

简单二维数组，范围显然接受不了。简单 cdq。

矩阵和，考虑二维前缀和差分，容易将一个 4-side 询问拆成四个 2-side 询问，于是就是三维偏序直接上 cdq。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define tup(x) array<int,(x)>
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
//void write(int x){cout<<x<<' ';}
//void write(pii x){cout<<"P("<<x.fi<<','<<x.se<<")\n";}
//void write(vector<auto>x){for(auto i:x)write(i);cout<<'\n';}
//void write(auto *a,int l,int r){for(int i=l;i<=r;i++)write(a[i]);cout<<'\n';}
inline ll lowbit(ll x){return x&-x;}
#define pcount(x) __builtin_popcount(x)
inline void cmx(ll &x,ll y){if(y>x)x=y;}
inline void cmn(ll &x,ll y){if(y<x)x=y;}
const int mod=998244353;
#define b(x) (x).begin()
ll qp(ll x,int y){ll res=1;for(;y;x=x*x%mod,y>>=1)if(y&1)res=res*x%mod;return res;}
const int N=2e5+5,M=2e6+5;
struct node{int op,x,y,v,f;};
int n,t[M],tot,ans[N];vector<node>q;
void upd(int x,int d){for(;x<=n;x+=lowbit(x))t[x]+=d;}
int ask(int x){int res=0;for(;x;x-=lowbit(x))res+=t[x];return res;}
bool cmp(node x,node y){return x.x<y.x;}
void cdq(int L,int R){if(L==R)return;int mid=L+R>>1;cdq(L,mid),cdq(mid+1,R);sort(b(q)+L,b(q)+1+mid,cmp),sort(b(q)+1+mid,b(q)+1+R,cmp);vector<pii>w;for(int l=L,r=mid+1;r<=R;r++){while(l<=mid&&q[l].x<=q[r].x)(q[l].op==1?upd(q[l].y,q[l].v),w.pb(mp(q[l].y,q[l].v)),1:0),++l;if(q[r].op==2)ans[q[r].v]+=ask(q[r].y)*q[r].f;}for(pii i:w)upd(i.fi,-i.se);
}
inline void UesugiErii(){cin>>n,cin>>n;q.pb(node{});int op,x,y,x_,y_,z;while(cin>>op){if(op==3)break;cin>>x>>y;if(op==1)cin>>z,q.pb(node{1,x,y,z});else ++tot,cin>>x_>>y_,q.pb(node{2,x-1,y-1,tot,1}),q.pb(node{2,x-1,y_,tot,-1}),q.pb(node{2,x_,y-1,tot,-1}),q.pb(node{2,x_,y_,tot,1});}
//	for(node i:q)cout<<i.op<<' '<<i.x<<' '<<i.y<<' '<<i.v<<'\n';cdq(1,q.size()-1);for(int i=1;i<=tot;i++)cout<<ans[i]<<'\n'; 
}
signed main(){//IO();//cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}