ABC281E数据结构线段树动态开点STL-Set

线段树代码

#include <stdio.h>
const int N=200005, M=1e9+7, T=N<<5;
int n, m, c, p, i, j, k, cnt, a[N], t[T], lc[T], rc[T];
long long s[T];
void add(int &p, int l, int r, int k, int x){
    if(!p) p = ++cnt;
    s[p] += k*x, t[p] += x;
    if(l < r){
        int m=l+r>>1;
        if(k <= m) add(lc[p], l, m, k, x);
        else add(rc[p], m+1, r, k, x);
    }
}
long long he(int p, int l, int r, int c){
    int m=l+r>>1, z=t[lc[p]];
    if(l == r) return 1ll*r*c;//只取c个
    if(c < z) return he(lc[p], l, m, c);
    if(c == z) return s[lc[p]];//整棵子树
    return he(rc[p], m+1, r, c-z) + s[lc[p]];
}//返回子树p的前c个数之和
int main(){
    scanf("%d%d%d", &n, &m, &c);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        add(p, 1, M, a[i], 1);//a[i]处增加一个数
        if(i > m) add(p, 1, M, a[i-m], -1);
        if(i >= m) printf("%lld ", he(p, 1, M, c));
    }
    return 0;
}

STL代码：一种迭代器

#include <bits/stdc++.h>
using namespace std;
int n, m, c, i, j, k, a[200005];
long long x;
multiset <int> s, t;
multiset <int> :: iterator p, q;
int main(){
    scanf("%d%d%d", &n, &m, &c);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        t.insert(a[i]);//存储c以上的
        if(i < m) continue;
        if(i > m){
            p = t.find(a[i-m]);
            if(p != t.end()) t.erase(p);
            else s.erase(s.find(a[i-m])), x -= a[i-m];
        }//删除a[i-m]，优先删除t里面的，s里面要减少x 
        if(s.size() && t.size()){//末尾最大p、开头最小q 
            p = s.end(), p--, q = t.begin();
            if(*q < *p) s.insert(*q), x += *q, t.erase(q);
        }//维护s最大值都要比t最小值小，t中至多一个大的
        while(s.size() < c){
            p = t.begin(), s.insert(*p);
            x += *p, t.erase(p);
        }//数量不对，多退少补
        while(s.size() > c){
            p = s.end(), p--, t.insert(*p);
            x -= *p, s.erase(p);
        }
        printf("%lld ", x);
    }
    return 0;
}

STL代码：两种迭代器

#include <bits/stdc++.h>
using namespace std;
int n, m, c, i, j, k, a[200005];
long long x;
multiset <int> s, t;
int main(){
    scanf("%d%d%d", &n, &m, &c);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        t.insert(a[i]);//存储c以上的
        if(i < m) continue;
        if(i > m){
            auto p = t.find(a[i-m]);
            if(p != t.end()) t.erase(p);
            else s.erase(s.find(a[i-m])), x -= a[i-m];
        }//删除a[i-m]，c以内要减少x
        if(s.size() && t.size()){
            auto p = s.rbegin();//末尾最大
            auto q = t.begin();//开头最小
            if(*q < *p) s.insert(*q), x += *q, t.erase(q);
        }//可能少一个，如果t中最小比s中最大大，转到s
        while(s.size() != c){
            auto p = s.rbegin();
            auto q = t.begin();
            if(s.size() < c) s.insert(*q), x += *q, t.erase(q);
            else t.insert(*p), x -= *p, s.erase(s.find(*p));//类型必须是迭代器？
        }//数量不对，多退少补
        printf("%lld ", x);
    }
    return 0;
}

暴力二分查找

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n, m, c, v, i, j, k, a[N], b[N], p[N];
long long s;
void cun(int x){
    if(!v) b[++v] = x, s += x;
    else{
        k = upper_bound(b+1, b+v+1, x) - b;
        if(k > v){
            b[++v] = x;
            if(v <= c) s += x;
        }
        else{
            memmove(b+k+1, b+k, 4*(v-k+1));
            b[k] = x, v++;
            if(k <= c) s += x - b[c+1];
        }
    }
}
void del(int x){
    k = lower_bound(b+1, b+v+1, x) - b;
    if(k <= c) s += b[c+1] - x;
    memmove(b+k, b+k+1, 4*(v-k));
    b[v--] = 0;
}
int main(){
    scanf("%d%d%d", &n, &m, &c);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        cun(a[i]);
        if(i > m) del(a[i-m]);
        if(i >= m) printf("%lld ", s);
    }
    return 0;
}