萌新求调教马蜂/调教树套树模板代码

#include<bits/stdc++.h>
#define mid ((le+ri)>>1)
using namespace std;
const int N=1e5+5,V=1e5;
struct nd{
	int a,b,c,v;
	vector<int> id;
	bool operator<(const nd &x)const{
		if(a!=x.a) return a<x.a;
		if(b!=x.b) return b<x.b;
		return c<x.c;
	}
}q[N];
struct sgt1{
	int s[N*300],ls[N*300],rs[N*300];
	int rt[N<<4],cnt;
	void push_up(int u){
		s[u]=s[ls[u]]+s[rs[u]];
	}
	void add(int &u,int le,int ri,int x,int k){
		if(!u) u=++cnt;
		if(le==ri){
			s[u]+=k;
			return;
		} 
		if(x<=mid) add(ls[u],le,mid,x,k);
		else add(rs[u],mid+1,ri,x,k);
		push_up(u);
	}
	int que(int u,int le,int ri,int x,int y){
		if(x<=le&&ri<=y){
			return s[u];
		}
		int res=0;
		if(x<=mid) res+=que(ls[u],le,mid,x,y);
		if(y>mid) res+=que(rs[u],mid+1,ri,x,y);
		return res;
	}
	void upd_f(int pos,int x,int k){
		add(rt[pos],1,V,x,k);
	}
	int que_f(int pos,int x,int y){
		return que(rt[pos],1,V,x,y);
	}
}t1;
struct sgt2{
	int s[N<<4];
	void ins(int u,int le,int ri,int x,int y,int k){
		t1.upd_f(u,y,k);
		if(le==ri) return;
		if(x<=mid) ins(2*u,le,mid,x,y,k);
		else ins(2*u+1,mid+1,ri,x,y,k);
	}
	int que(int u,int le,int ri,int x,int y,int cx,int cy){
		if(x<=le&&ri<=y){
			return t1.que_f(u,cx,cy);
		}
		int res=0;
		if(x<=mid) res+=que(2*u,le,mid,x,y,cx,cy);
		if(y>mid) res+=que(2*u+1,mid+1,ri,x,y,cx,cy);
		return res; 
	}
}t2;
int n,m,ans[N],rec[N];
struct init{
	int a[N],b[N],c[N];
	map<array<int,3>,vector<int>> mp;
	vector<int> ha,hb,hc;
	void dec(int n,int a[]){
		vector<int> h;
		for(int i=1;i<=n;i++){
			h.push_back(a[i]);
		}
		sort(h.begin(),h.end());
		auto lt=unique(h.begin(),h.end());
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(h.begin(),lt,a[i])-h.begin()+1;
		}
	}
	void mian(){
		int maxn;
		cin>>m>>maxn;
		for(int i=1;i<=m;i++){
			cin>>a[i]>>b[i]>>c[i];
		}
		dec(m,a),dec(m,b),dec(m,c);
		for(int i=1;i<=m;i++){
			mp[{a[i],b[i],c[i]}].push_back(i);
		}
		for(auto tp:mp){
			auto ms=tp.first;
			int x=ms[0],y=ms[1],z=ms[2],w=tp.second.size();
			q[++n]={x,y,z,w,tp.second};
		}
		sort(q+1,q+n+1);
	}
}f1;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	f1.mian();
	for(int i=1;i<=n;i++){
		int b=q[i].b,c=q[i].c,v=q[i].v;
		t2.ins(1,1,V,b,c,v);
		int w=t2.que(1,1,V,1,b,1,c);
		for(int j:q[i].id){
			ans[j]=w;
			rec[w]++;
		}
	}
	for(int i=1;i<=m;i++){
		cout<<rec[i]<<"\n";
	}
}