CF813E Army Creation

ゝ一纸荒年。 2021-09-30 01:12 282阅读 0赞

昨天想了好久……现在想想是水题啊。

首先对于一个区间，如果一个数出现的次数超过了$k$次， 那么直接选$k$个这个数就好了。然后我们算一算每一个数对答案的贡献，对于第$i$个下标的数$a\_i$，它只会对它之前出现不超过$k$次的区间产生贡献，那么弄一个队列记录一下每一个数的出现次数就好了。

扫过去的时候先把这个数的位置$+1$，然后看看它是不是出现超过了$k$次，如果是的话就把它第$k + 1$次前出现的位置$-1$，查询就是相当于查询区间和，用一个线段树维护就好了。

这题要强制在线，所以离线排序的方法并不行，直接把这个线段树可持久化。

时间复杂度$O((n + q)logn)$。

Code：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N = 1e5 + 5;
    
    int n, qn, K, maxn = 0, a[N];
    queue <int> q[N];
    
    inline void read(int &X) {
        X = 0; char ch = 0; int op = 1;
        for(; ch > '9' || ch < '0'; ch = getchar())
            if(ch == '-') op = -1;
        for(; ch >= '0' && ch <= '9'; ch = getchar())
            X = (X << 3) + (X << 1) + ch - 48;
        X *= op;
    }
    
    inline void swap(int &x, int &y) {
        int t = x; x = y; y = t;
    }
    
    namespace PSegT {
        struct Node {
            int lc, rc, sum;
        } s[N * 60];
        
        int root[N], nodeCnt = 0;
        
        #define mid ((l + r) >> 1)
        #define lc(p) s[p].lc
        #define rc(p) s[p].rc
        #define sum(p) s[p].sum
        
        void ins(int &p, int l, int r, int x, int v, int pre) {
            s[p = ++nodeCnt] = s[pre], sum(p) += v;
            if(l == r) return;
            
            if(x <= mid) ins(lc(p), l, mid, x, v, lc(pre));
            else ins(rc(p), mid + 1, r, x, v, rc(pre));
        }
        
        int query(int r1, int r2, int l, int r, int x, int y) {
            if(x <= l && y >= r) return sum(r2) - sum(r1);
            
            int res = 0;
            if(x <= mid) res += query(lc(r1), lc(r2), l, mid, x, y);
            if(y > mid) res += query(rc(r1), rc(r2), mid + 1, r, x, y);
            
            return res;
        }
        
    } using namespace PSegT;
    
    int main() {
        read(n), read(K);
        for(int i = 1; i <= n; i++) {
            read(a[i]);
            ins(root[i], 1, n, i, 1, root[i - 1]);
            q[a[i]].push(i);
            if(q[a[i]].size() > (unsigned)K) {
                ins(root[i], 1, n, q[a[i]].front(), -1, root[i]);
                q[a[i]].pop();
            }
        }
        
        read(qn);
        for(int x, y, ans = 0; qn--; ) {
            read(x), read(y);
            x = (x + ans) % n + 1, y = (y + ans) % n + 1;
            if(x > y) swap(x, y);
            printf("%d\n", ans = query(root[x - 1], root[y], 1, n, x, y));
        }
        
        return 0;
    }

转载于:https://www.cnblogs.com/CzxingcHen/p/9661162.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/5f1c950eaa91424aa00a5e01ace4c07f.png