链接 https://codeforces.com/problemset/problem/911/G
大意: 给定序列, 每次操作将区间 [l,r] 中的 x 全改为 y, 最后输出序列
权值范围比较小, 对每个权值开一颗线段树, 每次将 x 合并到 y 上即可
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #define REP(i,a,n) for(int i=a;i<=n;++i)
- #define mid (l+r>>1)
- #define lc (o<<1)
- #define rc (lc|1)
- using namespace std;
- typedef long long ll;
- const int N = 2e5+10;
- int a[N], n, m, t;
- int rt[110], tot, ql, qr, now;
- struct _ {int l,r;}v[N<<5];
- void ins(int &o, int l, int r, int pos) {
- if (!o) o=++tot;
- if (l==r) return;
- if (mid>=pos) ins(v[o].l,l,mid,pos);
- else ins(v[o].r,mid+1,r,pos);
- }
- int merge(int x, int y) {
- if (!x||!y) return x^y;
- v[x].l = merge(v[x].l,v[y].l);
- v[x].r = merge(v[x].r,v[y].r);
- return x;
- }
- void update(int &x, int &y, int l, int r) {
- if (!x) return;
- if (ql<=l&&r<=qr) return y=merge(x,y),void(x=0);
- if (!y) y=++tot;
- if (mid>=ql) update(v[x].l,v[y].l,l,mid);
- if (mid<qr) update(v[x].r,v[y].r,mid+1,r);
- }
- void dfs(int o, int l, int r) {
- if (!o) return;
- if (l==r) return void(a[l]=now);
- dfs(v[o].l,l,mid),dfs(v[o].r,mid+1,r);
- }
- int main() {
- scanf("%d", &n);
- REP(i,1,n) {
- int t;
- scanf("%d", &t);
- ins(rt[t],1,n,i);
- }
- scanf("%d", &m);
- while (m--) {
- int x, y;
- scanf("%d%d%d%d", &ql, &qr, &x, &y);
- if (x!=y) update(rt[x],rt[y],1,n);
- }
- REP(i,1,100) now=i,dfs(rt[i],1,n);
- REP(i,1,n) printf("%d",a[i]);
- puts("");
- }
来源: http://www.bubuko.com/infodetail-2962366.html