BZOJ4418: [Shoi2013]扇形面积并

#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) a[x].data
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define MAXN 100010
using namespace std;
int n,m,q,d=0;
struct Segment_Tree{
	int data,l,r;
}a[MAXN<<2];
struct Fan{
	int r,x,c;
}b[MAXN<<2];
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
inline bool cmp(const Fan &p,const Fan &q){
	return p.x<q.x;
}
inline void add(int r,int x,int y){
	d++;
	b[d].r=r;b[d].x=x;b[d].c=1;
	d++;
	b[d].r=r;b[d].x=y;b[d].c=-1;
}
inline void pushup(int rt){
	DATA(rt)=DATA(LSON)+DATA(RSON);
}
inline void buildtree(int l,int r,int rt){
	LSIDE(rt)=l;RSIDE(rt)=r;
	if(l==r){
		DATA(rt)=0;
		return;
	}
	int mid=l+r>>1;
	buildtree(l,mid,LSON);
	buildtree(mid+1,r,RSON);
	pushup(rt);
}
void update(int l,int r,int c,int rt){
	if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
		DATA(rt)+=c;
		return;
	}
	int mid=LSIDE(rt)+RSIDE(rt)>>1;
	if(l<=mid)update(l,r,c,LSON);
	if(mid<r)update(l,r,c,RSON);
	pushup(rt);
}
int query(int k,int rt){
	if(k<=0)return 0;
	if(DATA(rt)<k)return 0;
	if(LSIDE(rt)==RSIDE(rt))return LSIDE(rt);
	if(k<=DATA(LSON))return query(k,LSON);
	else return query(k-DATA(LSON),RSON);
}
void work(){
	long long ans=0;
	for(int i=1;i<=d;i++){
		if(i>1){
			int k=query(DATA(1)-q+1,1);
			if(k)ans+=1LL*k*k*(b[i].x-b[i-1].x);
		}
		update(b[i].r,b[i].r,b[i].c,1);
	}
	printf("%lld\n",ans);
}
void init(){
	int r,x,y,maxn=0;
	n=read();m=read();q=read();
	for(int i=1;i<=n;i++){
		r=read();x=read();y=read();
		x+=m;y+=m;
		maxn=max(maxn,r);
		if(x<=y)add(r,x,y);
		else{
			add(r,0,y);
			add(r,x,(m<<1));
		}
	}
	sort(b+1,b+d+1,cmp);
	buildtree(1,maxn,1);
}
int main(){
	init();
	work();
    return 0;
}