YZOJ P3942 gss2加强版
时间限制：2000MS 内存限制：524288KB
难度：\(7.0\)
-
题目描述
给你 \(n\) 个数，你需要支持一下两种操作。
U x y：将第 \(x\) 个数修改成 \(y\) ；
Q x y：计算从第 \(x\) 个数至第 \(y\) 个数中不同数的和并输出。如对于一段数 \(1,2,3,2,7\)，它的值是 \(13=1+2+3+7\) 。
-
输入格式
第一行 \(n\) 表示数的个数；
第二行包含这 \(n\) 个数；
第三行 \(m\) 表示操作次数；
接下来 \(m\) 行每行三个数表示题目描述的操作。
-
输出格式
对于每个 Q 操作返回一个值。
-
样例输入
|
1 2 3 4 5 6 |
5 1 2 4 2 3 3 Q 2 4 U 4 7 Q 2 4 |
-
样例输出
|
1 2 |
6 13 |
-
数据规模与约定
所有的输入均在 int 以内。
\(n \leq 100000 , m \leq 100000\)
Source： BZOJ 2883
思想类似于 P3706 ，求区间内不同数的和 等价于 区间内第一次出现的数的和。
所以可以维护每个位置上 上一个与它数值相同的位置 \(pre\)，对于区间 \([l, r]\) ，若有 \(pre < l\) 则可以加入答案。
显然修改时会影响到其它位置的前驱，所以对于每种数用 std::set 维护相同数的位置。
询问相当于把每个位置看成二维坐标系中的一个点 \(\left(pre,i\right)\) ，并求 \(x \in [0, l-1], y \in [l, r]\) 的所有点的 \(a_i\) 之和。
显然可以用二维线段树维护。
还有一种线段树套平衡树的做法，空间复杂度会比较小。
时间复杂度都为 \(O(n \log^2 n)\) 。
|
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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> inline int getnum() { register char c=0; while(!(c>='0' && c<='9') && c!='U' && c!='Q') c=getchar(); if(c=='U') return 0; else if(c=='Q') return 1; register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int val[205050],lv; #define GetValMap(_a) (std::lower_bound(&val[1],&val[lv+1],_a)-&val[0]) int a[105050],pre[105050]; #define _SIZE 27778888 int cnt,root[105050],lson[_SIZE],rson[_SIZE]; long long smv[_SIZE]; int MP,MV; void ModifyTree(int&o,register int l,register int r) { if(!o) o=++cnt; if(l==r) { smv[o]=MV; return; } register int mid=(l+r)>>1; if(MP <= mid) ModifyTree(lson[o],l,mid); else ModifyTree(rson[o],mid+1,r); smv[o]=smv[lson[o]]+smv[rson[o]]; } int QL,QR; long long _Qret; void QueryTree(register int o,register int l,register int r) { if(!o) return; if(QL<=l && QR>=r) { _Qret+=smv[o]; return; } register int mid=(l+r)>>1; if(QL <= mid) QueryTree(lson[o],l,mid); if(QR > mid) QueryTree(rson[o],mid+1,r); } int N; #define _lowbit(_x) ((_x)&-(_x)) inline void ModifyFTree(register int o) { //printf("modify %d, %d from %d to %d\n",o,MP,a[MP],MV); o++; while(o <= N) { ModifyTree(root[o],1,N); o+=_lowbit(o); } } inline long long QueryFTree(register int o) { //printf("query %d, [%d, %d]\n",o,QL,QR); _Qret=0,o++; while(o) { QueryTree(root[o],1,N); o-=_lowbit(o); } return _Qret; } typedef __gnu_pbds::tree<int,__gnu_pbds::null_type> _t; typedef _t::point_iterator _it; _t pos[200005]; bool opt[105050]; int qx[105050],qy[105050]; int main() { register int N=getnum(); ::N=N; for(register int i=1;i<=N;i++) val[++lv]=a[i]=getnum(); register int M=getnum(); for(register int i=1;i<=M;i++) { opt[i]=getnum(),qx[i]=getnum(),qy[i]=getnum(); if(opt[i] == 0) val[++lv]=qy[i]; } std::sort(&val[1],&val[lv+1]); lv=std::unique(&val[1],&val[lv+1])-&val[0]; for(register int i=1,t;i<=N;i++) { _it it=pos[t=GetValMap(a[i])].insert(i).first; pre[i]=(it==pos[t].begin() ? 0 : *(--it)); MP=i,MV=a[i],ModifyFTree(pre[i]); } for(register int i=1,t;i<=M;i++) if(opt[i] == 0) { register int x=qx[i],y=qy[i]; _it nit=pos[t=GetValMap(a[x])].find(x),pit=nit++,it=pit--; if(nit != pos[t].end()) { MP=*nit,MV=0,ModifyFTree(pre[*nit]); pre[*nit]=(it==pos[t].begin() ? 0 : *pit); MP=*nit,MV=a[*nit],ModifyFTree(pre[*nit]); } pos[t].erase(it); a[x]=y; nit=pos[t=GetValMap(a[x])].insert(x).first,pit=nit++,it=pit--; if(nit != pos[t].end()) { MP=*nit,MV=0,ModifyFTree(pre[*nit]); pre[*nit]=*it; MP=*nit,MV=a[*nit],ModifyFTree(pre[*nit]); } MP=x,MV=0,ModifyFTree(pre[x]); pre[x]=(it==pos[t].begin() ? 0 : *pit); MP=x,MV=a[x],ModifyFTree(pre[x]); } else QL=qx[i],QR=qy[i],printf("%lld\n",QueryFTree(qx[i]-1)); return 0; } |