求助

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,m,k;
struct scanline{
	int x,y,w;
	inline bool operator<(const scanline &a)const{
		if(y!=a.y)return y<a.y;
		return w>a.w;
	}
}sl[MAXN*2];
vector<int> Q;
struct tree{
	int l,r,val,w;
}t[MAXN*4];
inline void push_up(int i){
	t[i].val=min(t[i*2].val,t[i*2+1].val);
}
inline void build(int i,int l,int r){
	t[i].l=l,t[i].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
}
inline void push_down(int i){
	if(t[i].w){
		t[i*2].w+=t[i].w,t[i*2].val+=t[i].w;
		t[i*2+1].w+=t[i].w,t[i*2+1].val+=t[i].w;
		t[i].w=0;
	}
}
inline void modify(int i,int l,int r,int w){
	if(Q[t[i].l-1]>=r||Q[t[i].r]<=l)return;
	if(Q[t[i].l-1]>=l&&Q[t[i].r]<=r){
		t[i].val+=w,t[i].w+=w;
		return;
	}
	push_down(i);
	modify(i*2,l,r,w),modify(i*2+1,l,r,w);
	push_up(i);
}
inline int query(int i,int sz){
	if(t[i].l==t[i].r){
		if(t[i].val<k)return sz;
		return Q[t[i].r];
	}
	push_down(i);
	if(t[i*2].val>=k)return query(i*2+1,Q[t[i*2].r]);
	else return query(i*2,sz);
}
signed main(){
//	freopen("1.in","r",stdin);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	Q.push_back(0);
	int tot=0;
	for(int i=1,r,a1,a2;i<=n;i++){
		cin>>r>>a1>>a2;
		if(a1<a2){
			sl[++tot]=(scanline){r,a1,1};
			sl[++tot]=(scanline){r,a2,-1};
		}else{
			sl[++tot]=(scanline){r,a1,1};
			sl[++tot]=(scanline){r,m,-1};
			sl[++tot]=(scanline){r,-m,1};
			sl[++tot]=(scanline){r,a2,-1};
		}
		Q.push_back(r);
	}
	sort(Q.begin(),Q.end());
	Q.erase(unique(Q.begin(),Q.end()),Q.end());
	sort(sl+1,sl+1+tot);
	build(1,1,Q.size()-1);
	int sum=0;
	sl[tot+1].y=m;
	for(int i=1;i<=tot;i++){
		modify(1,0,sl[i].x,sl[i].w);
		int alpha=(sl[i+1].y-sl[i].y),r=query(1,0);
		sum+=alpha*r*r;
	}
	cout<<sum;
}

#include<bits/stdc++.h>
using namespace std;
int n=10000,m=1000000,k;
mt19937 rd(time(nullptr));
inline int Rand(int l,int r){
	int tmp=rd()%(r-l+1);
	return tmp+l;
}
signed main(){
	freopen("1.in","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	k=Rand(1,5000);
	cout<<n<<" "<<m<<" "<<k<<'\n';
	for(int i=1;i<=n;i++){
		int a1=Rand(-m,m),a2=Rand(-m,m);
		cout<<Rand(1,n)<<" "<<a1<<" "<<a2<<'\n';
	}
}