性感K-D tree TLE 20pts求调
查看原帖
性感K-D tree TLE 20pts求调
545835
TTpandaS楼主2023/11/30 18:24
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x;
}
const int N=1e5+5,mod=1e9+7;
const double alph=0.75;
int n,qnum;
struct node{
	int val[2];
	int sum,sum2;
}a[N];
struct tree{
	int lc,rc;
	int siz;
	int minn[2],maxn[2];
	int sum,sum2;
	node val;
}t[4*N];
int flag;
int operator<(node x,node y){
	return x.val[flag]<y.val[flag];
}
struct Q{
	int op,x,y;
}q[N];
stack<int> rub;
int ncnt;
int newnode(){
	int k;
	if(!rub.empty()){
		k=rub.top();
		rub.pop();
	}
	else{
		k=++ncnt;
	}
	return k;
}
void pushup(int k){
	int lc=t[k].lc,rc=t[k].rc;
	for(int i=0;i<=1;i++){
		t[k].maxn[i]=t[k].minn[i]=t[k].val.val[i];
		if(lc){
			t[k].minn[i]=min(t[k].minn[i],t[lc].minn[i]);
			t[k].maxn[i]=max(t[k].maxn[i],t[lc].maxn[i]);
		}
		if(rc){
			t[k].minn[i]=min(t[k].minn[i],t[rc].minn[i]);
			t[k].maxn[i]=max(t[k].maxn[i],t[rc].maxn[i]);			
		}
	}
	t[k].siz=t[lc].siz+t[rc].siz+1;
	t[k].sum=t[k].val.sum+t[lc].sum+t[rc].sum;
	t[k].sum%=mod;
	t[k].sum2=t[k].val.sum2+t[lc].sum2+t[rc].sum2;
	t[k].sum2%=mod;
}
int build(int l,int r,int f){
	if(l>r){
		return 0;
	}
	int k=newnode(),mid=(l+r)>>1;
	flag=f;
	nth_element(a+l,a+mid,a+r+1);
	t[k].val=a[mid];
	t[k].lc=build(l,mid-1,f^1);
	t[k].rc=build(mid+1,r,f^1);
	pushup(k);
	return k;
}
void rebuild(int k,int siz){
	int lc=t[k].lc,rc=t[k].rc;
	if(lc){
		rebuild(lc,siz);
	}
	a[siz+t[lc].siz+1]=t[k].val;
	rub.push(k);
	if(rc){
		rebuild(rc,siz+t[lc].siz+1);
	}
}
int check(int k,int f){
	int lc=t[k].lc,rc=t[k].rc;
	if(alph*t[k].siz<t[lc].siz||alph*t[k].siz<t[rc].siz){
		rebuild(k,0);
		k=build(1,t[k].siz,f);
	}
	return k;
}
int add(node tmp,int k,int f){
	if(!k){
		k=newnode();
		t[k].val=tmp;
		t[k].lc=t[k].rc=0;
		pushup(k);
		return k;
	}
	if(t[k].val.val[f]<tmp.val[f]){
		t[k].rc=add(tmp,t[k].rc,f^1);
	}
	else{
		t[k].lc=add(tmp,t[k].lc,f^1);
	}
	pushup(k);
	k=check(k,f);
	return k;
}
bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
	return x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2;
}
bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
	return x1>X2||x2<X1||y1>Y2||y2<Y1;
}
pair<int,int> ask(int k,int x1,int y1,int x2,int y2){
	if(!k){
		return {0,0};
	}
	if(in(x1,y1,x2,y2,t[k].minn[0],t[k].minn[1],t[k].maxn[0],t[k].maxn[1])){
		return {t[k].sum,t[k].sum2};
	}
	if(out(x1,y1,x2,y2,t[k].minn[0],t[k].minn[1],t[k].maxn[0],t[k].maxn[1])){
		return {0,0};
	}
	int res=0,res2=0;
	if(in(x1,y1,x2,y2,t[k].val.val[0],t[k].val.val[1],t[k].val.val[0],t[k].val.val[1])){
		res+=t[k].val.sum;
		res%=mod;
		res2+=t[k].val.sum2;
		res2%=mod;		
	}
	pair<int,int> p1=ask(t[k].lc,x1,y1,x2,y2),p2=ask(t[k].rc,x1,y1,x2,y2);
	res+=p1.first+p2.first;
	res2+=p1.second+p2.second;
	return {res,res2};
}
int A[N],B[N],x[N],y[N];
int ans[N];
int now[N];
void Dhxqvq(){
	n=read(),qnum=read();
	for(int i=1;i<=n;i++){
		A[i]=read(),B[i]=read();
		a[i].val[0]=A[i],a[i].sum=B[i];
		a[i].val[1]=i,a[i].sum2=1;
		now[i]=i;
	}
	for(int i=1;i<=qnum;i++){
		x[i]=read(),y[i]=read();
	}
}
void Dhxqwq(){
	int rt=build(1,n,0);
	for(int i=1;i<=n;i++){
		pair<int,int> p=ask(rt,1,i+1,A[now[i]]-1,n);
		ans[0]=(ans[0]+p.first+p.second*B[now[i]]%mod)%mod;
	}
	for(int i=1;i<=qnum;i++){
		ans[i]=ans[i-1];
		pair<int,int> p,p1;
		p=ask(rt,1,x[i]+1,A[now[x[i]]]-1,n);
		p1=ask(rt,A[now[x[i]]]+1,1,n,x[i]-1);
		ans[i]=(((ans[i]-p.first+mod)%mod-p.second*B[now[x[i]]]%mod+mod)%mod-p1.first+mod-p1.second*B[now[x[i]]]%mod+mod)%mod;
		p=ask(rt,1,y[i]+1,A[now[y[i]]]-1,n);
		p1=ask(rt,A[now[y[i]]]+1,1,n,y[i]-1);
		ans[i]=(((ans[i]-p.first+mod)%mod-p.second*B[now[y[i]]]%mod+mod)%mod-p1.first+mod-p1.second*B[now[y[i]]]%mod+mod)%mod;
		if(A[now[x[i]]]>A[now[y[i]]]&&x[i]<y[i]){
			ans[i]=((ans[i]+B[now[x[i]]])%mod+B[now[y[i]]])%mod;
		}
		if(A[now[y[i]]]>A[now[x[i]]]&&y[i]<x[i]){
			ans[i]=((ans[i]+B[now[x[i]]])%mod+B[now[y[i]]])%mod;
		}
		rt=add(node{A[now[x[i]]],x[i],-B[now[x[i]]],-1},rt,0);
		rt=add(node{A[now[y[i]]],y[i],-B[now[y[i]]],-1},rt,0);
		rt=add(node{A[now[y[i]]],x[i],B[now[y[i]]],1},rt,0);
		rt=add(node{A[now[x[i]]],y[i],B[now[x[i]]],1},rt,0);
		p=ask(rt,1,x[i]+1,A[now[y[i]]]-1,n);
		p1=ask(rt,A[now[y[i]]]+1,1,n,x[i]-1);
		ans[i]=((((ans[i]+p.first)%mod+p.second*B[now[y[i]]]%mod)%mod+p1.first)%mod+p1.second*B[now[y[i]]]%mod)%mod;
		p=ask(rt,1,y[i]+1,A[now[x[i]]]-1,n);
		p1=ask(rt,A[now[x[i]]]+1,1,n,y[i]-1);
		ans[i]=((((ans[i]+p.first)%mod+p.second*B[now[x[i]]]%mod)%mod+p1.first)%mod+p1.second*B[now[x[i]]]%mod)%mod;
		if(A[now[x[i]]]>A[now[y[i]]]&&y[i]<x[i]){
			ans[i]=(ans[i]-B[now[x[i]]]+mod-B[now[y[i]]]+mod)%mod;
		}
		if(A[now[y[i]]]>A[now[x[i]]]&&x[i]<y[i]){
			ans[i]=(ans[i]-B[now[x[i]]]+mod-B[now[y[i]]]+mod)%mod;
		}
		swap(now[x[i]],now[y[i]]);
//		for(int j=1;j<=n;j++){
//			ans[i]+=ask(rt,1,j+1,A[now[j]]-1,n)+ask2(rt,1,j+1,A[now[j]]-1,n)*B[now[j]];
//			ans[i]%=mod;
//		}
	}
}
void Dhxqaq(){
	for(int i=1;i<=qnum;i++){
		printf("%lld\n",ans[i]);
	}
}
signed main(){
	Dhxqvq();
	Dhxqwq();
	Dhxqaq();
	return 0;
}
/*
5 5
1 1
2 2
3 3
5 4
4 5
1 5
1 5
2 4
5 3
1 3
*/
2023/11/30 18:24
加载中...