Lvat_s Blog

这题我在学校的OJ上A掉了，在BZOJ上WA了……很神奇

但是还是发一下代码吧，如果有什么错误欢迎各位老司机们指出

是一个树套树，外围像区间K大一样维护一个权值线段树，内部维护一个线段树记录这个值出现在哪些区间上

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

int n,m,cnt,root[500005];

struct SegTree{
int nl,nr,l,r,sum,tag;
}tree[20000005];

void Pushdown(int rt){
if(tree[rt].tag && tree[rt].l!=tree[rt].r){
	int mid=tree[rt].l+tree[rt].r>>1;
	if(!tree[rt].nl){tree[rt].nl=++cnt;tree[tree[rt].nl].l=tree[rt].l;tree[tree[rt].nl].r=mid;}
	if(!tree[rt].nr){tree[rt].nr=++cnt;tree[tree[rt].nr].l=mid+1;tree[tree[rt].nr].r=tree[rt].r;}
	tree[tree[rt].nl].tag+=tree[rt].tag;
	tree[tree[rt].nr].tag+=tree[rt].tag;
	tree[tree[rt].nl].sum+=(tree[tree[rt].nl].r-tree[tree[rt].nl].l+1)*tree[rt].tag;
	tree[tree[rt].nr].sum+=(tree[tree[rt].nr].r-tree[tree[rt].nr].l+1)*tree[rt].tag;
	tree[rt].tag=0;
}
}

void Pushup(int rt){
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

void Modify(int &rt,int l,int r,int L,int R){
if(!rt){rt=++cnt;tree[rt].l=l;tree[rt].r=r;}
Pushdown(rt);
if(L<=tree[rt].l && tree[rt].r<=R){
	tree[rt].sum+=tree[rt].r-tree[rt].l+1;
    tree[rt].tag++;
    return;
}
int mid=tree[rt].l+tree[rt].r>>1;
if(L<=mid)Modify(tree[rt].nl,l,mid,L,R);
if(R>mid)Modify(tree[rt].nr,mid+1,r,L,R);
Pushup(rt);
}

int Query(int rt,int l,int r){
if(!rt)return 0;
Pushdown(rt);
if(l<=tree[rt].l && tree[rt].r<=r){return tree[rt].sum;}
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Query(tree[rt].nl,l,r);
if(r>mid)ans+=Query(tree[rt].nr,l,r);
Pushup(rt);
return ans;
}

void Insert(int l,int r,int v){
int L=1,R=n,rt=1;
while(L!=R){
	int mid=L+R>>1;
	Modify(root[rt],1,n,l,r);
	if(v<=mid){R=mid;rt*=2;}
	else {L=mid+1;rt=rt*2+1;}
}
Modify(root[rt],1,n,l,r);
}

int Ask(int l,int r,int k){
int L=1,R=n,rt=1;
while(L!=R){
	int mid=L+R>>1;
	int ans=Query(root[rt*2],l,r);
	if(ans>=k){R=mid;rt*=2;}
	else {L=mid+1;rt=rt*2+1;k-=ans;}
}
return L;
}

int main(){
freopen("3110.in","r",stdin);
freopen("3110.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
    int opt,a,b,c;
    scanf("%d %d %d %d",&opt,&a,&b,&c);
    if(opt==1)Insert(a,b,n-c+1);
    if(opt==2)printf("%d\n",n-Ask(a,b,c)+1);
}
return 0;
}

这题其实一开始看的时候我是不会做的……

考虑Floyd,f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

那么我们考虑k的转移顺序，如果让k的点权严格上升,那么转移时增加的点权必定为v[i],v[j]或者v[k]。

那么直接Floyd就可以了。

以后想问题时一定要弄明白算法的本质，不然就会困难重重……

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

int n,m,K,v[255],dis[255][255],ans[255][255];

struct Point{
int x,y;
friend bool operator<(Point x,Point y){return x.y<y.y;}
}p[255];

int main(){
freopen("1774.in","r",stdin);
freopen("1774.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
memset(dis,127/3,sizeof(dis));
memset(ans,127/3,sizeof(ans));
for(int i=1;i<=n;i++){
	scanf("%d",&p[i].y);
	p[i].x=i;
	v[i]=p[i].y;
}
for(int i=1;i<=m;i++){
	int x,y,z;
	scanf("%d %d %d",&x,&y,&z);
	dis[x][y]=min(dis[x][y],z);
	dis[y][x]=min(dis[y][x],z);
}
sort(p+1,p+n+1);
for(int k=1;k<=n;k++){
	int l=p[k].x;
    for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]);
			ans[i][j]=min(ans[i][j],dis[i][j]+max(max(v[i],v[j]),v[l]));
		}
    }
}
for(int i=1;i<=K;i++){
	int x,y;
	scanf("%d %d",&x,&y);
	printf("%d\n",ans[x][y]);
}
return 0;
}

我做的第一道莫比乌斯反演！

照模版写的……题解复制自ACDreamer

-----------------------------------------------------------

我们知道莫比乌斯反演的一般描述为：

其实它还有另一种描述，本题也是用到这种。那就是：

好了，到了这里，我们开始进入正题。。。

对于本题，我们设

为满足且和的的对数

为满足且和的的对数

那么，很显然

反演后得到

--------------------------------------

然后我们对于莫比乌斯函数统计前缀和然后加一加就好了啦！

详细请看代码

#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,a,b,c,d,k,tab[50005],cnt,prime[50005],mu[50005],sum[50005];
 
void Mobius(int num){
mu[1]=1;
for(int i=2;i<=num;i++){
    if(!tab[i]){
        prime[++cnt]=i;
        mu[i]=-1;
    }
    for(int j=1;j<=cnt && i*prime[j]<=num;j++){
        tab[i*prime[j]]=1;
        if(i%prime[j])mu[i*prime[j]]=-mu[i];
        else {mu[i*prime[j]]=0;break;}
    }
}
}
 
int Solve(int x,int y){
int ans=0,cs=0;
if(x>y)swap(x,y);
for(int i=1;i<=x;i=cs+1){
    cs=min(x/(x/i),y/(y/i));
    ans+=(sum[cs]-sum[i-1])*(x/i)*(y/i);
}
return ans;
}
 
int main(){
freopen("2301.in","r",stdin);
freopen("2301.out","w",stdout);
scanf("%d",&n);
Mobius(50000);
for(int i=1;i<=50000;i++)sum[i]=sum[i-1]+mu[i];
while(n--){
    scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
    printf("%d\n",Solve(b/k,d/k)-Solve((a-1)/k,d/k)-Solve(b/k,(c-1)/k)+Solve((a-1)/k,(c-1)/k));
}
return 0;
}

容斥原理

计算近似幸运数字的个数，就是总个数减去不是近似幸运数字的数的个数

首先用一个dfs筛出所有10位以内的幸运数字，然后再把倍数筛掉

最后运用容斥原理，Dfs筛一遍就好了

这个Dfs是一个补集的容斥

具体请看代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
 
long long a,b,us[2505],siz,ne[2505],nen;
 
void dfs(int w,long long x){
if(w>10)return;
us[++siz]=x;
dfs(w+1,x*10ll+6);
dfs(w+1,x*10ll+8);
}
 
bool cmp(long long as,long long bs){
return as>bs;
}
 
long long gcd(long long s1,long long s2){
return !s2?s1:gcd(s2,s1%s2);
}
 
long long Dfs(int i,long long nu){
if(i>nen)return b/nu-a/nu;
long long ans=Dfs(i+1,nu),g=gcd(ne[i],nu);
if(nu/g<=b/ne[i])ans-=Dfs(i+1,nu/g*ne[i]);
return ans;
}
 
int main(){
freopen("1853.in","r",stdin);
freopen("1853.out","w",stdout);
scanf("%lld %lld",&a,&b);
dfs(1,6);
dfs(1,8);
sort(us+1,us+siz+1,cmp);
for(int i=1;i<=siz;i++){
    int flag=0;
    for(int j=siz;j>i;j--){
        if(us[i]%us[j]==0){
            flag=1;
            break;
        }
    }
    if(flag==0)ne[++nen]=us[i];
}
a--;
printf("%lld\n",b-a-Dfs(1,1));
return 0;
}

很久以前写的题目了……

SPFA

显然的算法啊

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
  
int fa[155][155],n,m,d,h[155],en=0,f[155][155];
double D[155][155];
  
struct Edge{
int b,v,l,next;
}e[30005];
  
struct Queue{
int speed,i,j;
};
  
void shuchu(int u,int v,int f){
if(u==v && v==0){printf("0 ");return;}
shuchu(fa[u][v],u,0);
if(f==0)printf("%d ",v);
else printf("%d\n",v);
}
  
void add(int as,int bs,int vs,int ls){
e[++en].b=bs;
e[en].v=vs;
e[en].l=ls;
e[en].next=h[as];
h[as]=en;
}
  
void spfa(){
queue<Queue> Q;
Queue pos;
pos.i=0;
pos.j=0;
pos.speed=70;
Q.push(pos);
int u,v;
D[0][0]=0;
f[0][0]=1;
while(!Q.empty()){
    Queue uu;
    uu=Q.front();
    u=uu.j;
    Q.pop();
    f[uu.i][u]=0;
    for(int i=h[uu.j];i;i=e[i].next){
        v=e[i].b;
        int speed=e[i].v;
        if(e[i].v<=0)speed=uu.speed;
        if(D[u][v]>D[uu.i][u]+(double)e[i].l/(double)speed){
            D[u][v]=D[uu.i][u]+(double)e[i].l/(double)speed;
            fa[u][v]=uu.i;
            if(!f[u][v]){
                f[u][v]=1;
                pos.i=u;
                pos.j=v;
                pos.speed=speed;
                Q.push(pos);
            }
        }
    }
}
}
  
int main(){
freopen("3245.in","r",stdin);
freopen("3245.out","w",stdout);
scanf("%d %d %d",&n,&m,&d);
memset(D,0x7f,sizeof(D));
for(int i=0;i<m;i++){
    int as,bs,vs,ls;
    scanf("%d %d %d %d",&as,&bs,&vs,&ls);
    add(as,bs,vs,ls);
}
spfa();
double mind=99999999999999.0;
int ans;
for(int i=0;i<n;i++){
    if(mind>D[i][d]){
        ans=i;
        mind=D[i][d];
    }
}
shuchu(ans,d,1);
return 0;
}

直接辛普森积分，我是照着nixy的模版写的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
 
int n;
const double eps=1e-9;
 
struct Circle{
double x,y,r;
friend bool operator<(Circle a,Circle b){
    return a.r<b.r;
}
}cir[1005];
 
struct Line{
double l,r;
Line(double kl=0,double kr=0){l=kl;r=kr;}
}line[1005];
 
double Dist(Circle a,Circle b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
 
bool cmp(Line a,Line b){
return a.l<b.l;
}
 
double F(double x){
int lx=0;
for(int i=1;i<=n;i++){
    double ex=(x-cir[i].x)*(x-cir[i].x);
    if(ex>cir[i].r)continue;
    ex=sqrt(cir[i].r-ex);
    line[++lx]=Line(cir[i].y-ex,cir[i].y+ex);
}
if(lx==0)return 0;
sort(line+1,line+lx+1,cmp);
double L=line[1].l,R=line[1].r,res=0;
for(int i=2;i<=lx;i++){
    if(line[i].l<=R){R=max(line[i].r,R);}
    else {res+=R-L;L=line[i].l;R=line[i].r;}
}
return res+R-L;
}
 
double Simpson(double l,double r,double Fl,double Fmid,double Fr){
return (Fl+Fr+4*Fmid)*(r-l)/6;
}
 
double Self_Adjust(double l,double r,double Fl,double Fmid,double Fr){
double mid=l/2+r/2;
double F1=F(l/2+mid/2),F2=F(mid/2+r/2);
if(r-l<2){
    double S1=Simpson(l,mid,Fl,F1,Fmid),S2=Simpson(mid,r,Fmid,F2,Fr),Se=Simpson(l,r,Fl,Fmid,Fr);
    if(fabs(Se-S1-S2)<eps)return S1+S2;
    else return Self_Adjust(l,mid,Fl,F1,Fmid)+Self_Adjust(mid,r,Fmid,F2,Fr);
}
else return Self_Adjust(l,mid,Fl,F1,Fmid)+Self_Adjust(mid,r,Fmid,F2,Fr);
}
 
int main(){
freopen("2178.in","r",stdin);
freopen("2178.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lf %lf %lf",&cir[i].x,&cir[i].y,&cir[i].r);
    cir[i].r*=cir[i].r;
}
printf("%.3lf\n",Self_Adjust(-2000,2000,F(-2000),F(0),F(2000)));
return 0;
}

这是我第一次写树状数组套可持久化数据结构，写了好长时间……

首先你需要AC POJ2104

然后把一个个递增的版本用树状数组维护就好了

为什么呢？因为你维护的是权值线段树，需要得到的值其实是作差得来的。

那么我们用类似树状数组的作差方法就可以了。

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

int siz,n,m,a[10005],tab[500005],tb,root[10005],A[10005],B[10005],An,Bn;

struct SegTree{
int nl,nr,sum;
}tree[2000005];

struct Ask{
int opt,l,r,k;
}ask[10005];

int lowbit(int x){return x&(-x);}

int Div(int x){
int l=1,r=tb;
while(l<=r){
	int mid=l+r>>1;
	if(tab[mid]<x)l=mid+1;
	else r=mid-1;
}
return l;
}

void AddTree(int lastrt,int l,int r,int &rt,int pos,int val){
if(rt==0)rt=++siz;
tree[rt].sum=tree[lastrt].sum+val;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
if(l==r)return;
int mid=l+r>>1;
if(pos<=mid)AddTree(tree[lastrt].nl,l,mid,tree[rt].nl,pos,val);
else AddTree(tree[lastrt].nr,mid+1,r,tree[rt].nr,pos,val);
}

int Sum(int l,int r,int k){
if(l==r)return l;
int sumL=0,sumR=0,mid=l+r>>1;
for(int i=1;i<=An;i++)sumL+=tree[tree[A[i]].nl].sum;
for(int i=1;i<=Bn;i++)sumR+=tree[tree[B[i]].nl].sum;
if(sumR-sumL>=k){
	for(int i=1;i<=An;i++)A[i]=tree[A[i]].nl;
	for(int i=1;i<=Bn;i++)B[i]=tree[B[i]].nl;
	return Sum(l,mid,k);
}
else {
	for(int i=1;i<=An;i++)A[i]=tree[A[i]].nr;
	for(int i=1;i<=Bn;i++)B[i]=tree[B[i]].nr;
	return Sum(mid+1,r,k-sumR+sumL);
}
}

int main(){
freopen("1901.in","r",stdin);
freopen("1901.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
	scanf("%d",&a[i]);
	tab[++tb]=a[i];
}
for(int i=1;i<=m;i++){
	char s[5];
    scanf("%s",s);
    if(s[0]=='C'){
		scanf("%d %d",&ask[i].l,&ask[i].k);
        ask[i].opt=1;
        tab[++tb]=ask[i].k;
    }
    if(s[0]=='Q'){
		scanf("%d %d %d",&ask[i].l,&ask[i].r,&ask[i].k);
		ask[i].opt=2;
		ask[i].l--;
    }
}
sort(tab+1,tab+tb+1);
tb=unique(tab+1,tab+tb+1)-tab-1;
for(int i=1;i<=n;i++){
    int x=Div(a[i]);
    for(int j=i;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,1);
}
for(int i=1;i<=m;i++){
	if(ask[i].opt==1){
		int x=Div(a[ask[i].l]);
		for(int j=ask[i].l;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,-1);
        a[ask[i].l]=ask[i].k;
        x=Div(ask[i].k);
		for(int j=ask[i].l;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,1);
	}
	else {
		An=Bn=0;
		for(int j=ask[i].l;j;j-=lowbit(j))A[++An]=root[j];
		for(int j=ask[i].r;j;j-=lowbit(j))B[++Bn]=root[j];
		printf("%d\n",tab[Sum(1,tb,ask[i].k)]);
	}
}
return 0;
}

好多水题的题解忘了传……

直接Treap

#include<cstdio>
#include<cstdlib>
 
int n,mn,tag=0,root,leave=0,cnt;
char s[2];
 
struct Treap{
    int l,r,v,rnd,siz,w;
}tree[100005];
 
void Pre(){
tree[0].l=0;
tree[0].r=0;
root=0;
cnt=0;
srand(123465);
}
 
void Pushup(int rt){
tree[rt].siz=tree[tree[rt].l].siz+tree[tree[rt].r].siz+tree[rt].w;
}
 
void Lr(int &p){
int q=tree[p].r;
tree[p].r=tree[q].l;
tree[q].l=p;
tree[q].siz=tree[p].siz;
Pushup(p);
p=q;
}
 
void Rr(int &p){
int q=tree[p].l;
tree[p].l=tree[q].r;
tree[q].r=p;
tree[q].siz=tree[p].siz;
Pushup(p);
p=q;
}
 
void Ins(int &rt,int x){
if(!rt){
    rt=++cnt;
    tree[rt].l=0;
    tree[rt].r=0;
    tree[rt].v=x;
    tree[rt].siz=1;
    tree[rt].w=1;
    tree[rt].rnd=rand()<<15+rand();
    return;
}
tree[rt].siz++;
if(tree[rt].v>x){
    Ins(tree[rt].l,x);
    if(tree[tree[rt].l].rnd<tree[rt].rnd)Rr(rt);
    return;
}
else {
    Ins(tree[rt].r,x);
    if(tree[tree[rt].r].rnd<tree[rt].rnd)Lr(rt);
}
}
 
int Del(int &rt){
if(rt==0)return 0;
if(tree[rt].v+tag<0){
    int temp=tree[tree[rt].l].siz+1;
    rt=tree[rt].r;
    return temp+Del(rt);
}
int temp=Del(tree[rt].l);
tree[rt].siz-=temp;
return temp;
}
 
int Find(int rt,int x){
if(rt==0)return 0;
if(x<=tree[tree[rt].l].siz)return Find(tree[rt].l,x);
else {
    if(x>tree[tree[rt].l].siz+1)return Find(tree[rt].r,x-tree[tree[rt].l].siz-1);
    return tree[rt].v+tag;
}
}
 
int main(){
freopen("1503.in","r",stdin);
freopen("1503.out","w",stdout);
scanf("%d %d",&n,&mn);
for(int i=1;i<=n;i++){
    int Ts;
    scanf("%s %d",s,&Ts);
    if(s[0]=='I'){if(Ts>=mn){Ins(root,Ts-tag-mn);}}
    if(s[0]=='A'){tag+=Ts;}
    if(s[0]=='S'){tag-=Ts;leave+=Del(root);}
    if(s[0]=='F'){if(Ts>tree[root].siz)puts("-1");else printf("%d\n",Find(root,tree[root].siz-Ts+1)+mn);}
}
printf("%d\n",leave);
return 0;
}

树链剖分直接上

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
int dep[100005],top[100005],id[100005],pre[100005],n,q,en,h[100005],fa[100005],son[100005],siz[100005],sn;
 
struct Edge{
int b,next;
}e[100005];
 
void AddEdge(int sa,int sb){
if(sa==sb)return;
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int tag,sum,l,r,rem;
}tree[400005];
 
void Pushdown(int rt){
if(tree[rt].rem){
    tree[rt*2].tag=0;
    tree[rt*2+1].tag=0;
    tree[rt*2].sum=0;
    tree[rt*2+1].sum=0;
    tree[rt].tag=0;
    tree[rt*2].rem=1;
    tree[rt*2+1].rem=1;
    tree[rt].rem=0;
}
if(tree[rt].tag){
    tree[rt*2].tag=1;
    tree[rt*2+1].tag=1;
    tree[rt*2].rem=0;
    tree[rt*2+1].rem=0;
    tree[rt*2].sum=tree[rt*2].r-tree[rt*2].l+1;
    tree[rt*2+1].sum=tree[rt*2+1].r-tree[rt*2+1].l+1;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
    tree[rt].rem=tree[rt].tag=tree[rt].sum=0;
    return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
tree[rt].rem=tree[rt].tag=tree[rt].sum=0;
}
 
void Add(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    tree[rt].tag=1;
    tree[rt].rem=0;
    tree[rt].sum=tree[rt].r-tree[rt].l+1;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Add(rt*2,l,r);
if(r>mid)Add(rt*2+1,l,r);
Pushup(rt);
}
 
void Del(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    tree[rt].rem=1;
    tree[rt].tag=0;
    tree[rt].sum=0;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Del(rt*2,l,r);
if(r>mid)Del(rt*2+1,l,r);
Pushup(rt);
}
 
int Sum(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    return tree[rt].sum;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Sum(rt*2,l,r);
if(r>mid)ans+=Sum(rt*2+1,l,r);
Pushup(rt);
return ans;
}
 
void dfs1(int u,int fat){
fa[u]=fat;
son[u]=0;
dep[u]=dep[fat]+1;
siz[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++sn;
pre[sn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==son[u] || v==fa[u])continue;
    dfs2(v,v);
}
}
 
int AddLine(int u){
int ans=0,f=top[u];
while(f!=1){
    ans+=id[u]-id[f]+1-Sum(1,id[f],id[u]);
    Add(1,id[f],id[u]);
    u=fa[f];
    f=top[u];
}
ans+=id[u]-id[1]+1-Sum(1,id[1],id[u]);
Add(1,id[1],id[u]);
return ans;
}
 
int DelSome(int u){
int ans=Sum(1,id[u],id[u]+siz[u]-1);
Del(1,id[u],id[u]+siz[u]-1);
return ans;
}
 
int main(){
freopen("4196.in","r",stdin);
freopen("4196.out","w",stdout);
scanf("%d",&n);
for(int i=2;i<=n;i++){
    int tp;
    scanf("%d",&tp);
    AddEdge(tp+1,i);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
    char s[10];
    int u;
    scanf("%s %d",s,&u);
    if(s[0]=='i')printf("%d\n",AddLine(u+1));
    else printf("%d\n",DelSome(u+1));
}
return 0;
}

水并查集

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

int t,n,f[1000005],g[1000005],index=0,ind;

struct Node{
int a,b,o;
}node[1000005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){if(x>y)f[x]=y;else f[y]=x;}

int main(){
freopen("4195.in","r",stdin);
freopen("4195.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ind=0;
for(int i=1;i<=n;i++){
	scanf("%d %d %d",&node[i].a,&node[i].b,&node[i].o);
	g[++ind]=node[i].a;
	g[++ind]=node[i].b;
}
sort(g+1,g+ind+1);
ind=unique(g+1,g+ind+1)-g-1;
for(int i=1;i<=n;i++){
	node[i].a=lower_bound(g+1,g+ind+1,node[i].a)-g;
	node[i].b=lower_bound(g+1,g+ind+1,node[i].b)-g;
}
for(int i=1;i<=ind;i++)f[i]=i;
for(int i=1;i<=n;i++){
	if(node[i].o==1){Union(Find(node[i].a),Find(node[i].b));}
}
int flag=0;
for(int i=1;i<=n;i++){
	if(node[i].o==0 && Find(node[i].a)==Find(node[i].b)){puts("NO");flag=1;break;}
}
if(!flag)puts("YES");
}
return 0;
}