Lvat_s Blog

卡常的kdtree……将标识符看为y轴上的对应的点，然后直接在kdtree上标记就可以了

被卡常了很悲伤……以下代码目前没有卡常卡过去先放着吧

------

UPD 2016.9.29

找管理员要来了数据……本机是9s不到(开O2)17s(不开O2)，到了bzoj上就是20s+……

我从14s+卡常卡到9s不到容易吗我……

就不能放宽点时限么……

没错我现在还是TLE

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define Add(x,y) (x=(x+y)%P)
#define Mul(x,y) (x=x*y%P)

const int N=50005;
const long long P=536870912ll;

int n,m,sort_tag,root,l,r;
long long x,y;

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

struct KDTree{
int d[2],mn[2],mx[2],ch[2];
long long add,mul,sum,v,siz;
KDTree(){mul=siz=1;sum=v=add=0;}
friend inline bool operator<(const KDTree &A,const KDTree &B){return A.d[sort_tag]<B.d[sort_tag];}
}tree[N];

inline void Pushdown(int rt){
if(tree[rt].mul!=1){
    if(tree[rt].ch[0]){
		Mul(tree[tree[rt].ch[0]].add,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].sum,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].mul,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].v,tree[rt].mul);
	}
    if(tree[rt].ch[1]){
		Mul(tree[tree[rt].ch[1]].add,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].sum,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].mul,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].v,tree[rt].mul);
	}
    tree[rt].mul=1;
}
if(tree[rt].add){
    if(tree[rt].ch[0]){
		Add(tree[tree[rt].ch[0]].add,tree[rt].add);
		Add(tree[tree[rt].ch[0]].sum,tree[rt].add*tree[tree[rt].ch[0]].siz%P);
		Add(tree[tree[rt].ch[0]].v,tree[rt].add);
	}
    if(tree[rt].ch[1]){
		Add(tree[tree[rt].ch[1]].add,tree[rt].add);
		Add(tree[tree[rt].ch[1]].sum,tree[rt].add*tree[tree[rt].ch[1]].siz%P);
		Add(tree[tree[rt].ch[1]].v,tree[rt].add);
	}
    tree[rt].add=0;
}
}

inline void Pushup_(int rt){
tree[rt].sum=tree[rt].siz=0;
if(tree[rt].ch[0]){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[0]].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[0]].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[0]].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[0]].mn[1]);
    Add(tree[rt].siz,tree[tree[rt].ch[0]].siz);
    Add(tree[rt].sum,tree[tree[rt].ch[0]].sum);
}
if(tree[rt].ch[1]){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[1]].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[1]].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[1]].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[1]].mn[1]);
    Add(tree[rt].siz,tree[tree[rt].ch[1]].siz);
    Add(tree[rt].sum,tree[tree[rt].ch[1]].sum);
}
Add(tree[rt].sum,tree[rt].v);
Add(tree[rt].siz,1ll);
}

int Build(int l,int r,int t){
int mid=l+r>>1;
sort_tag=t;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].ch[0]=Build(l,mid-1,t^1);
if(r>mid)tree[mid].ch[1]=Build(mid+1,r,t^1);
Pushup_(mid);
return mid;
}

void Addv(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(!tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    int mid=tree[rt].d[tag];
    if(l<mid)Addv(tree[rt].ch[0],tag^1);
    if(r>mid)Addv(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    if(l<=tree[rt].mx[!tag])Addv(tree[rt].ch[0],tag^1);
    if(r>=tree[rt].mn[!tag])Addv(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}

void Addv2(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    int mid=tree[rt].d[tag];
    if(l<mid)Addv2(tree[rt].ch[0],tag^1);
    if(r>mid)Addv2(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    if(l<=tree[rt].mx[!tag])Addv2(tree[rt].ch[0],tag^1);
    if(r>=tree[rt].mn[!tag])Addv2(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}

long long Sum(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(!tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
    int mid=tree[rt].d[tag];
    if(l<mid)ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
    if(r>mid)ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
    return ans;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
    if(l<=tree[rt].mx[!tag])ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
    if(r>=tree[rt].mn[!tag])ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
    return ans;
}
}

long long Sum2(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
    int mid=tree[rt].d[tag];
    if(l<mid)ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
    if(r>mid)ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
    return ans;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
    if(l<=tree[rt].mx[!tag])ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
    if(r>=tree[rt].mn[!tag])ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
    return ans;
}
}

int main(){
freopen("4303.in","r",stdin);
freopen("4303.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(tree[i].d[1]);tree[i].d[0]=i;}
root=Build(1,n,1);
while(m--){
    static int opt;
    Read(opt);Read(l);Read(r);
    if(opt==0){Read(x);Read(y);Addv(root,1);}
    if(opt==1){Read(x);Read(y);Addv2(root,1);}
    if(opt==2){printf("%lld\n",Sum(root,1));}
    if(opt==3){printf("%lld\n",Sum2(root,1));}
}
return 0;
}

啊

去年NOIP惨不忍睹的回忆

不讲了，暴力dfs就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=15;

int test,n,a[N],ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsa(int x,int y){
if(x==0){ans=min(ans,y);return;}
for(int i=1;i<=14;i++)if(a[i]>0)y+=a[i];
ans=min(ans,y);return;
}

void dfsb(int x,int y){
if(x==0){ans=min(ans,y);return;}
if(a[14]>=2){
	a[14]-=2;
	dfsb(x-2,y+1);
	a[14]+=2;
}
dfsa(x,y);
}

void dfsc(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=13;i++){
	if(a[i]>=2){
		a[i]-=2;
		dfsc(x-2,y+1,i);
		a[i]+=2;
	}
}
dfsb(x,y);
}

void dfsd(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		a[i]-=3;
		dfsd(x-3,y+1,i);
		a[i]+=3;
	}
}
dfsc(x,y);
}

void dfse(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
		a[i]-=4;
		dfse(x-4,y+1,i);
		a[i]+=4;
	}
}
dfsd(x,y);
}

void dfsf(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=14;j++){
			if(j==i)continue;
			else if(a[j]>=1){
				a[i]-=3;
				a[j]--;
				dfsf(x-4,y+1,i);
				a[i]+=3;
				a[j]++;
			}
		}
	}
}
dfse(x,y);
}

void dfsg(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=13;j++){
			if(j==i)continue;
			else if(a[j]>=2){
				a[i]-=3;
				a[j]-=2;
				dfsg(x-5,y+1,i);
				a[i]+=3;
				a[j]+=2;
			}
		}
	}
}
dfsf(x,y);
}

void dfsh(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=8;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]==0)break;
        if(j>=5){
            for(int k=1;k<=j;k++)a[i+k-1]--;
            dfsh(x-j,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]++;
        }
    }
}
dfsg(x,y);
}

void dfsi(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=10;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<2)break;
        if(j>=3){
            for(int k=1;k<=j;k++)a[i+k-1]-=2;
            dfsi(x-j*2,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=2;
        }
    }
}
dfsh(x,y);
}

void dfsj(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=11;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<3)break;
        if(j>=2){
            for(int k=1;k<=j;k++)a[i+k-1]-=3;
            dfsj(x-j*3,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=3;
        }
    }
}
dfsi(x,y);
}

void dfsk(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=14;j++){
			if(i==j || a[j]==0)continue;
			for(int k=1;k<=14;k++){
				if(i==k || j==k || a[k]==0)continue;
				a[i]-=4;
				a[j]--;
				a[k]--;
				dfsk(x-6,y+1,i);
				a[i]+=4;
				a[j]++;
				a[k]++;
			}
        }
        for(int j=1;j<=14;j++){
			if(i==j)continue;
			if(a[j]<2)continue;
            a[i]-=4;
            a[j]-=2;
            dfsk(x-6,y+1,i);
            a[i]+=4;
            a[j]+=2;
        }
	}
}
dfsj(x,y);
}

void dfsl(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=13;j++){
			if(i==j || a[j]<2)continue;
			for(int k=1;k<=13;k++){
				if(i==k || j==k || a[k]<2)continue;
				a[i]-=4;
				a[j]-=2;
				a[k]-=2;
				dfsl(x-8,y+1,i);
				a[i]+=4;
				a[j]+=2;
				a[k]+=2;
			}
        }
        for(int j=1;j<=13;j++){
			if(i==j && a[j]<8)continue;
            if(a[j]<4)continue;
            a[i]-=4;
            a[j]-=4;
            dfsl(x-8,y+1,i);
			a[i]+=4;
			a[j]+=4;
        }
	}
}
dfsk(x,y);
}

int main(){
freopen("4325.in","r",stdin);
freopen("4325.out","w",stdout);
Read(test);Read(n);
while(test--){
	memset(a,0,sizeof(a));
    for(register int i=1;i<=n;i++){
		int x,y;
		Read(x);Read(y);
		if(x==0)a[14]++;
		else if(x>2)a[x-2]++;
		else a[x+11]++;
    }
	ans=n;
	dfsl(1,0);
	printf("%d\n",ans);
}
return 0;
}

考虑用两个set来维护Hash值

一个维护当前有哪些房间里面有人

一个维护哪些Hash值已经被查询过了

然后直接按照操作要求一步步做就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,q,a[N],tx[N],siz[N];
long long Mp[N],Room[N];
set<long long> Hash;
set<int> St;
 
template<typename T>inline int Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
 
void Read_Char(char &x){
while((x=getchar())<'A' || x>'Z');
}
 
inline int Rand_int(){return (rand()<<15)|rand();}
inline long long Rand_ll(){return ((1ll*Rand_int())<<31ll)+Rand_int();}
 
inline void Change(const int &l,const int &r){
Room[tx[l]]^=Mp[l];
siz[tx[l]]--;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
tx[l]=r;
Room[tx[l]]^=Mp[l];
siz[tx[l]]++;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
}
 
inline int Query(const int &l,const int &r){
int ans=0;
static set<int>::iterator I;
while(1){
    I=St.lower_bound(l);
    if(I==St.end() || *I>r)break;
    ans+=siz[*I];
    Hash.insert(Room[*I]);
    St.erase(I);
}
return ans;
}

int main(){
freopen("3578.in","r",stdin);
freopen("3578.out","w",stdout);
Read(n);Read(m);Read(q);siz[1]=n;
for(register int i=1;i<=n;i++){
    Mp[i]=Rand_ll();
    Room[1]^=Mp[i];
    tx[i]=1;
}
St.insert(1);
while(q--){
    static int l,r;
    static char chs;
    Read_Char(chs);Read(l);Read(r);
    if(chs=='C')Change(l,r);
    else printf("%d\n",Query(l,r));
}
return 0;
}

我是纸张……

自以为考虑到所有的情况了，但是却在2操作后忘记给主树加边了……

55555555555555……

-----------

这题虽然可以用高明的数据结构做但是也可以用块状树写。我写的就是块状树

把树分成若干块，父节点的块大小没到要求就加到父节点的块里面去。

这样貌似会被星形的数据卡掉但是既然过了也就不管了

定义原来的树为主树

对于块和块之间连接形成的树称为辅树

加点时一定要在辅树和主树中都更新！

然后对于辅树的每个节点维护一个数据结构(我用了vector,实际上可以是treap等平衡树而且效果肯定更好)

先把本块内的数据查询完然后往下直接走整块

就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=60005,block_size=200;

int n,lastans,m,en,h[N],w[N],belong[N],block_num,fa[N],bh[N];

struct Edge{int b,next;}e[N<<1];
inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
inline void AddBkEg(int sa,int sb){e[++en].b=sb;e[en].next=bh[sa];bh[sa]=en;}

struct Node{
vector<int> Vx;int siz;
Node(){siz=0;}
inline void Insert(int x){if(!siz)Vx.push_back(x);else Vx.insert(upper_bound(Vx.begin(),Vx.end(),x),x);siz++;}
inline void Change(int x,int y){Vx.erase(lower_bound(Vx.begin(),Vx.end(),x));Insert(y);}
inline int Query(int x){return Vx.end()-upper_bound(Vx.begin(),Vx.end(),x);}
}block[N];

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsp(int u,int fat){
if(block[belong[fat]].siz<block_size)belong[u]=belong[fat];
else belong[u]=++block_num,AddBkEg(belong[fat],belong[u]);
block[belong[u]].Insert(w[u]);
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fat)continue;
	fa[v]=u;
	dfsp(v,u);
}
}

void dfsb(int u,int x){
lastans+=block[u].Query(x);
for(int i=bh[u];i;i=e[i].next)dfsb(e[i].b,x);
}

void dfss(int u,int x){
if(w[u]>x)lastans++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
    if(v==fa[u])continue;
    if(belong[v]==belong[u])dfss(v,x);
    else dfsb(belong[v],x);
}
}

int main(){
freopen("3720.in","r",stdin);
freopen("3720.out","w",stdout);
Read(n);
for(register int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(register int i=1;i<=n;i++)Read(w[i]);
dfsp(1,0);
Read(m);
while(m--){
    int opt,u,v;
    Read(opt);Read(u);Read(v);
    u^=lastans;v^=lastans;
    if(opt==0){lastans=0;dfss(u,v);printf("%d\n",lastans);}
    if(opt==1){block[belong[u]].Change(w[u],v);w[u]=v;}
    if(opt==2){w[++n]=v;AddEdge(u,n);if(block[belong[u]].siz<block_size)belong[n]=belong[u];else belong[n]=++block_num,AddBkEg(belong[u],belong[n]);block[belong[n]].Insert(v);fa[n]=u;}
}
return 0;
}

这题是我当初学习CDQ分治时候的神级题目……当时不会做一直拖到现在

这题是动态维护最小生成树，但是是可以离线的，所以我们用CDQ分治对操作进行分治

每一层内用两个操作进行维护

$Contraction$:删除必定在最小生成树中的边并把贡献进行统计(不修改的情况下)

$Reduction$:删除必定不在最小生成树中的边(不修改的情况下)

这样到最后统计时边集的规模就已经相当小了，可以暴力Kruskal统计

但是边集是不断变化的很麻烦所以我们每层建一个边集就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=20005,M=50005,Lg2=22,INF=1000000000;

int n,m,q,siz[N],f[N],a[M],sum[M],c[M];
long long ans[M];

struct Edge{
int u,v,w,id;
inline friend bool operator<(const Edge &A,const Edge &B){return A.w<B.w;}
}e[Lg2][M],d[M],t[M];

struct Query{
int x,y;
}que[M];

inline void Clear(const int &cnt){for(register int i=1;i<=cnt;i++){f[d[i].u]=f[d[i].v]=0;siz[d[i].u]=siz[d[i].v]=1;}}
int Find(int x){return !f[x]?x:f[x]=Find(f[x]);}
inline void Merge(int x,int y){x=Find(x);y=Find(y);if(siz[x]>siz[y])f[y]=x,siz[x]+=siz[y];else f[x]=y,siz[y]+=siz[x];}

inline void Reduction(int &tot){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++){
    if(Find(d[i].u)!=Find(d[i].v)){
		Merge(d[i].u,d[i].v);
		d[++tp]=d[i];
		c[d[i].id]=tp;
    }
    else if(d[i].w==INF){
        d[++tp]=d[i];
        c[d[i].id]=tp;
    }
}
tot=tp;
}

inline void Contraction(int &tot,long long &val){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){Merge(d[i].u,d[i].v);t[++tp]=d[i];}
for(register int i=1;i<=tp;i++)f[t[i].u]=f[t[i].v]=0,siz[t[i].u]=siz[t[i].v]=1;
for(register int i=1;i<=tp;i++)if(Find(t[i].u)!=Find(t[i].v) && t[i].w!=-INF){Merge(t[i].u,t[i].v);val+=t[i].w;}
tp=0;
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){d[++tp]=d[i];c[d[i].id]=tp;d[tp].u=Find(d[tp].u);d[tp].v=Find(d[tp].v);}
tot=tp;
}

void CDQ(int l,int r,int now,long long val){
int tot=sum[now];
if(l==r)a[que[l].x]=que[l].y;
for(register int i=1;i<=tot;i++)e[now][i].w=a[e[now][i].id];
for(register int i=1;i<=tot;i++)d[i]=e[now][i],c[d[i].id]=i;
if(l==r){
	ans[l]=val;
    Clear(tot);
    sort(d+1,d+tot+1);
	for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v))ans[l]+=d[i].w,Merge(d[i].u,d[i].v);
    return;
}
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=-INF;
Contraction(tot,val);
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=INF;
Reduction(tot);
sum[now+1]=tot;
for(register int i=1;i<=tot;i++)e[now+1][i]=d[i];
int mid=l+r>>1;
CDQ(l,mid,now+1,val);CDQ(mid+1,r,now+1,val);
}

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

int main(){
freopen("2001.in","r",stdin);
freopen("2001.out","w",stdout);
Read(n);Read(m);Read(q);sum[0]=m;
for(register int i=1;i<=m;i++)Read(e[0][i].u),Read(e[0][i].v),Read(a[i]),e[0][i].id=i,e[0][i].w=a[i];
for(register int i=1;i<=q;i++)Read(que[i].x),Read(que[i].y);
CDQ(1,q,0,0);
for(register int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}

本来想用树状数组+主席树水过去的……20min码完后发现空间炸了

卡了几发空间后发现自己并不会卡空间的高明技巧就弃疗了

后来写了一个CDQ分治就水过去了

主席树做法就不说了

CDQ分治主要就是按照位置划分第一层，按照时间(操作顺序)划分第二层，按照值划分第三层

第一层我们读入进来的就是有序的所以不用管

第二次我们可以用CDQ分治分治第二层

分治时用树状数组统计第三层

最后递归前要还原树状数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int L[N],R[N],BIT[N],time,n,m,pos[N];
long long ans[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Operation{
int t,a,b;
}a[N],b[N];

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){BIT[x]+=y;x+=lowbit(x);}}
inline int Sum(int x){int ans=0;while(x){ans+=BIT[x];x-=lowbit(x);}return ans;}

void CDQ(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
int Lx=l,Rx=mid+1;
for(register int i=l;i<=r;i++){
	if(a[i].t<=mid)b[Lx++]=a[i];
	else b[Rx++]=a[i];
}
Lx=l,Rx=mid;
for(register int i=mid+1;i<=r;i++){
	for(;Lx<=mid && b[Lx].a<=b[i].a;Lx++)Add(b[Lx].b,1);
	L[b[i].t]+=Lx-l-Sum(b[i].b);
}
for(register int i=l;i<Lx;i++)Add(b[i].b,-1);
for(register int i=r;i>mid;i--){
	for(;Rx>=l && b[Rx].a>b[i].a;Rx--)Add(b[Rx].b,1);
	R[b[i].t]+=Sum(b[i].b-1);
}
for(register int i=Rx+1;i<=mid;i++)Add(b[i].b,-1);
for(register int i=l;i<=r;i++)a[i]=b[i];
CDQ(l,mid);CDQ(mid+1,r);
}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);time=n;
for(register int i=1;i<=n;i++)Read(a[i].b),a[i].a=i,pos[a[i].b]=i;
for(register int i=1;i<=m;i++){int x;Read(x);a[pos[x]].t=time--;}
for(register int i=1;i<=n;i++)if(!a[i].t)a[i].t=time--;
CDQ(1,n);
for(register int i=1;i<=n;i++)ans[i]=ans[i-1]+L[i]+R[i];
for(register int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);
return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,BIT[N],cnt,a[N],b[N],ls[N*108],rs[N*108],sum[N*108],q[N],bq[N],pts;
long long ans,an[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Pushup(const int &rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];}

void Insert(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]+1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid)Insert(ls[rt],ls[lrt],l,mid,v);
if(v>mid)Insert(rs[rt],rs[lrt],mid+1,r,v);
Pushup(rt);
}

void Delete(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]-1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid){if(sum[ls[rt]]==1){ls[rt]=0;return;}Delete(ls[rt],ls[lrt],l,mid,v);}
if(v>mid){if(sum[rs[rt]]==1){rs[rt]=0;return;}Delete(rs[rt],rs[lrt],mid+1,r,v);}
Pushup(rt);
}

long long FindU(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return sum[rs[rt]]+FindU(ls[rt],l,mid,v);
return FindU(rs[rt],mid+1,r,v);
}

long long FindD(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return FindD(ls[rt],l,mid,v);
return sum[ls[rt]]+FindD(rs[rt],mid+1,r,v);
}

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){Insert(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline void Del(int x,int y){while(x<=n){Delete(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline long long SumU(int x,int y){long long ans=0;while(x){ans+=FindU(BIT[x],1,n,y);x-=lowbit(x);}return ans;}
inline long long SumD(int x,int y){long long ans=0;while(x){ans+=FindD(BIT[x],1,n,y);x-=lowbit(x);}return ans;}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(a[i]);b[a[i]]=i;}
for(register int i=1;i<=m;i++){Read(q[i]);bq[q[i]]=1;}
for(register int i=1;i<=n;i++){
	if(bq[a[i]])continue;
	Add(i,a[i]);
	ans+=SumU(i,a[i])+SumD(n,a[i])-SumD(i-1,a[i]);
}
an[++pts]=ans;
for(register int i=m;i;i--){
	Add(b[q[i]],q[i]);
	ans+=SumU(b[q[i]],q[i])+SumD(n,q[i])-SumD(b[q[i]]-1,q[i]);
    an[++pts]=ans;
}
for(register int i=pts;i>1;i--)printf("%lld\n",an[i]);
return 0;
}