2020-2021:teams:mian:withinlover:mos_algorithm

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:mian:withinlover:mos_algorithm [2020/05/21 22:06]
withinlover
+++ 2020-2021:teams:mian:withinlover:mos_algorithm [2020/05/21 22:09] (当前版本)
withinlover [题解]
@@ 行 83: / 行 83: @@
 考虑时间的修改，记录下修改的位置和颜色，如果不在当前区间内直接修改，如果在当前区间内，可以等价为一次区间增加和一次区间减小。
+对了，这题卡常。需要写的常数很小才能过。
+<hidden Code>
+<codedoc code:c++>
+#include <cmath>
+#include <cstdio>
+#include <iostream>
+#include <algorithm>
+const int N = 150000;
+const int M = 1e6 + 100;
+inline int read() {
+    int q=0,w=1;char c=getchar();
+    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
+    while(c>='0'&&c<='9')q=(q<<1)+(q<<3)+(c^48),c=getchar();
+    return w*q;
+}
+inline void swap(int &x,int &y){x=x^y;y=x^y;x=x^y;}
+char s[5];
+int n, m, i, j, l, r, t, ans, blk, cntQ, cntR;
+int pos[N], val[N], cnt[M], a[N], Ans[N], tmp[N];
+struct Que{
+    int l, r, idl, idr, t, pos;
+    inline bool operator < (const Que &b) const {
+        if(idl ^ b.idl) return idl < b.idl;
+        if(idr ^ b.idr) return idr < b.idr;
+        return t < b.t;
+    }
+} Q[N];
+int main() {
+    n = read(); m = read(); blk=ceil(pow(n,0.75));
+    for(i = 1;i <= n; ++i)
+        a[i] = read();
+    for(i = blk;i <= n; ++i) tmp[i] = tmp[i - blk] + 1;
+    for(i = 1;i <= m; ++i) {
+        scanf("%s", s);
+        if(s[0]=='Q') {
+            cntQ++;
+            Q[cntQ].l = read();
+            Q[cntQ].r = read();
+            Q[cntQ].idl = tmp[Q[cntQ].l];
+            Q[cntQ].idr = tmp[Q[cntQ].r];
+            Q[cntQ].t = cntR;
+            Q[cntQ].pos = cntQ;
+        } else {
+            cntR++;
+            pos[cntR] = read();
+            val[cntR] = read();
+        }
+    }
+    std::sort(Q + 1, Q + 1 + cntQ);l = 1; r = 0; t = 0; ans = 0;
+    for(i = 1;i <= cntQ; ++i) {
+        int ql = Q[i].l, qr = Q[i].r, qt = Q[i].t;
+        while(l < ql) ans -= !--cnt[a[l++]];
+        while(l > ql) ans += !cnt[a[--l]]++;
+        while(r < qr) ans += !cnt[a[++r]]++;
+        while(r > qr) ans -= !--cnt[a[r--]];
+        while(t < qt) {
+            t++;
+            if(l <= pos[t] && pos[t] <= r) ans -= !--cnt[a[pos[t]]] - !cnt[val[t]]++;
+            swap(a[pos[t]], val[t]);
+        }
+        while(t > qt) {
+            if(l <= pos[t] && pos[t] <= r) ans -= !--cnt[a[pos[t]]] - !cnt[val[t]]++;
+            swap(a[pos[t]], val[t]);
+            --t;
+        }
+        Ans[Q[i].pos] = ans;
+    }
+    for(i = 1;i <= cntQ; ++i)
+        printf("%d\n", Ans[i]);
+    return 0;
+}
+</codedoc>
+</hidden>

2020-2021/teams/mian/withinlover/mos_algorithm.1590069976.txt.gz · 最后更改: 2020/05/21 22:06 由 withinlover