性感K-Dtree在线求查,(常数)很大,40pts
查看原帖
性感K-Dtree在线求查,(常数)很大,40pts
545835
TTpandaS楼主2023/11/30 21:43
#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
template<typename type>
inline void write(type x,bool mode=1){
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}
const int N=1e5+5;
const long long mod=1e9+7;
const double alph=0.75;
int n,qnum;
struct node{
	int val[2];
	long long sum,sum2;
}a[N];
struct tree{
	int lc,rc;
	int siz;
	int minn[2],maxn[2];
	long long 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;
}
inline 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+mod)%mod;
	t[k].sum2=(t[k].val.sum2+t[lc].sum2+t[rc].sum2+mod)%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;
}
inline 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<long long,long long> 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};
	}
	long long 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=(res+t[k].val.sum)%mod;
		res2=(res2+t[k].val.sum2)%mod;
	}
	pair<long long,long long> 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];
long long B[N];
int x[N],y[N];
long long ans[N];
int now[N];
inline void Dhxqvq(){
	n=rd(),qnum=rd();
	for(int i=1;i<=n;++i){
		A[i]=rd(),B[i]=rd();
		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]=rd(),y[i]=rd();
	}
}
inline void Dhxqwq(){
	int rt=build(1,n,0);
	for(int i=1;i<=n;++i){
		pair<long long,long long> p=ask(rt,1,i+1,A[now[i]]-1,n);
		ans[0]=((ans[0]+p.first)%mod+p.second*B[now[i]]%mod)%mod;
	}
	for(int i=1;i<=qnum;++i){
		ans[i]=ans[i-1];
		pair<long long,long long> 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)%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)%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)%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)%mod-B[now[y[i]]]+mod)%mod;
		}
		swap(now[x[i]],now[y[i]]);
	}
}
inline void Dhxqaq(){
	for(int i=1;i<=qnum;++i){
		write(ans[i],1);
	}
}
signed main(){
//	freopen("8.in","r",stdin);
//	freopen("dhx.out","w",stdout);
	Dhxqvq();
	Dhxqwq();
	Dhxqaq();
	return 0;
}
2023/11/30 21:43
加载中...