1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| #include <bits/stdc++.h> #define MAXN 1000005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace SegmentTree{ struct node{ int l,r; int val; int lval,rval,sum; }tree[MAXN*30]; #define lc tree[i].l #define rc tree[i].r inline void pushup(int i,int x,int y){ tree[i].lval=tree[x].lval; tree[i].rval=tree[y].rval; tree[i].sum=tree[x].sum+tree[y].sum; if (tree[x].rval==1&&tree[y].lval==1) tree[i].sum--; } int tot; void Update(int &i,int l,int r,int pos){ if (!i) i=++tot; if (l==r){ tree[i].lval=tree[i].rval=tree[i].sum=1; return ; } int mid=(l+r)>>1; if (pos<=mid) Update(lc,l,mid,pos); else Update(rc,mid+1,r,pos); pushup(i,lc,rc); } void Merge(int &x,int &y){ if (!x||!y){ x=x+y; return ; } Merge(tree[x].l,tree[y].l); Merge(tree[x].r,tree[y].r); pushup(x,tree[x].l,tree[x].r); y=0; } } using namespace SegmentTree; map<int,int>rt; int main(){ #define SUM(c) tree[rt[c]].sum int n=read(),m=read(); for (register int i=1;i<=n;++i){ int color=read(); Update(rt[color],1,n,i); } int ans=0; for (const auto& it:rt){ ans+=SUM(it.first); } for (register int i=1;i<=m;++i){ int opr=read(); if (opr==1){ int x=read(),y=read(); if (x==y||!rt[x]) continue; if (!rt[y]){ rt[y]=rt[x]; rt[x]=0; continue; } ans-=SUM(x),ans-=SUM(y); Merge(rt[y],rt[x]); ans+=SUM(y); } else { printf("%d\n",ans); } } }
|