CDQ分治
模板
cpp
int t[N],n,k;
void add(int x,int y){
for(int i=x;i<=k;i+=i&-i)t[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i;i&=i-1)ans+=t[i];
return ans;
}
struct Node{
int a,b,c,cnt,res=0;
bool operator<(const Node&tmp)const{
if(a!=tmp.a)return a<tmp.a;
if(b!=tmp.b)return b<tmp.b;
return c<tmp.c;
}
bool operator==(const Node&tmp)const{
return a==tmp.a&&b==tmp.b&&c==tmp.c;
}
} a[N],b[N];
void msort(int l,int r){
if(l==r)return;
int mid=l+r>>1;
msort(l,mid),msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(a[i].b<=a[j].b)add(a[i].c,a[i].cnt),b[k++]=a[i++];
else a[j].res+=query(a[j].c),b[k++]=a[j++];
}
while(i<=mid)add(a[i].c,a[i].cnt),b[k++]=a[i++];
while(j<=r)a[j].res+=query(a[j].c),b[k++]=a[j++];
for(int i=l;i<=mid;i++)add(a[i].c,-a[i].cnt);
for(int i=l;i<=r;i++)a[i]=b[i];
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].b>>a[i].c,a[i].cnt=1;
sort(a+1,a+n+1);
int j=1;
for(int i=1;i<=n;i++){
if(a[i]==a[j-1])a[j-1].cnt++;
else a[j++]=a[i];
}
msort(1,j-1);
map<int,int> ans;
for(int i=1;i<j;i++)ans[a[i].res+a[i].cnt-1]+=a[i].cnt;
for(int i=0;i<n;i++)cout<<ans[i]<<"\n";
}cdq分治离线求解二维数点问题
- 多加一维z，原图的点z=0，查询点z=1
cpp
struct Node{
int x,y,z,p,id,op,res;
bool operator<(const Node&tmp)const{
if(x!=tmp.x)return x<tmp.x;
if(y!=tmp.y)return y<tmp.y;
return z<tmp.z;
}
};
vector<Node> a,b;
void msort(int l,int r){
if(l==r)return;
int mid=l+r>>1;
msort(l,mid),msort(mid+1,r);
int i=l,j=mid+1,k=l;
int sum=0;
while(i<=mid&&j<=r){
if(a[i].y<=a[j].y)sum+=a[i].p,b[k++]=a[i++];
else a[j].res+=sum,b[k++]=a[j++];
}
while(i<=mid)sum+=a[i].p,b[k++]=a[i++];
while(j<=r)a[j].res+=sum,b[k++]=a[j++];
for(int i=l;i<=r;i++)a[i]=b[i];
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int x,y,p;
cin>>x>>y>>p;
a.push_back({x,y,0,p,0,0,0});
}
for(int i=1;i<=m;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
a.push_back({x2,y2,1,0,i,1,0});
a.push_back({x2,y1-1,1,0,i,-1,0});
a.push_back({x1-1,y2,1,0,i,-1,0});
a.push_back({x1-1,y1-1,1,0,i,1,0});
}
sort(a.begin(),a.end());
b=a;
msort(0,a.size()-1);
vector<int> ans(m+1);
for(auto [x,y,z,p,id,op,res]:a){
if(id)ans[id]+=op*res;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}普通二维数点问题
- 对原点和查询点按x排序
- 权值树状数组计数
cpp
int a[N],c[N];
void add(int x,int y){
for(int i=x;i<N;i+=i&-i)c[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i;i&=i-1)ans+=c[i];
return ans;
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int> ans(m+1);
vector<array<int,3>> q[n+1];
for(int i=1;i<=m;i++){
int l,r,x;
cin>>l>>r>>x;
q[l-1].push_back({i,x,-1});
q[r].push_back({i,x,1});
}
for(int i=1;i<=n;i++){
add(a[i],1);
for(auto &[id,x,op]:q[i])ans[id]+=op*query(x);
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}动态逆序对
- 加多一维时间戳，时间戳越大越早删除
cpp
struct Node{
int val,ts,res;
bool operator<(const Node&tmp)const{
if(val!=tmp.val)return val<tmp.val;
return ts<tmp.ts;
}
};
int t[N];
void add(int x,int y){
for(int i=x;i<N;i+=i&-i)t[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i;i&=i-1)ans+=t[i];
return ans;
}
vector<Node> a,b;
void msort(int l,int r){
if(l==r)return;
int mid=l+r>>1;
msort(l,mid),msort(mid+1,r);
int i=mid,j=r,k=l;
//t[i]<t[j],pos[i]<pos[j],A[i]>A[j]
while(i>=l&&j>mid){
//val值从小到大排序，因此这里倒序枚举
if(a[i].val>a[j].val)add(a[i].ts,1),i--;
else a[j].res+=query(a[j].ts-1),j--;
}
while(i>=l)add(a[i].ts,1),i--;
while(j>mid)a[j].res+=query(a[j].ts-1),j--;
for(int i=l;i<=mid;i++)add(a[i].ts,-1);
j=l,i=mid+1;
//t[i]<t[j],pos[i]>pos[j],A[i]<A[j]
while(j<=mid&&i<=r){
if(a[i].val<a[j].val)add(a[i].ts,1),i++;
else a[j].res+=query(a[j].ts-1),j++;
}
while(j<=mid)a[j].res+=query(a[j].ts-1),j++;
while(i<=r)add(a[i].ts,1),i++;
for(int i=mid+1;i<=r;i++)add(a[i].ts,-1);
i=l,j=mid+1;
//归并排序
while(i<=mid&&j<=r){
if(a[i].val<a[j].val)b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
for(int i=l;i<=r;i++)a[i]=b[i];
}
void solve(){
int n,m;
cin>>n>>m;
vector<int> pos(n+1);
for(int i=0;i<n;i++){
int x;
cin>>x;
pos[x]=i;
a.push_back({x,0});
}
int ts=n;
for(int i=1;i<=m;i++){
int x;
cin>>x;
a[pos[x]].ts=ts--;
}
for(int i=0;i<n;i++){
if(a[i].ts==0)a[i].ts=ts--;
}
b=a;
msort(0,n-1);
vector<int> ans(n+1);
for(int i=0;i<n;i++)ans[a[i].ts]+=a[i].res;
for(int i=1;i<=n;i++)ans[i]+=ans[i-1];
for(int i=n;i>n-m;i--)cout<<ans[i]<<"\n";
}