CF627E Orchestra

https://www.luogu.com.cn/problem/CF627E

考虑扫描线，枚举上界，拓展下界，显然不太好做（不知道能不能用阴间数据结构干过去）

考虑反过来
枚举上界，下界从下往上移动，那么加点就变成了删点，这个可以用链表轻松维护

具体实现可以用$gs[x]$表示往左$k$个跳到$x$的右端点个数

注意链表的实现，0要特判

code:

#include<bits/stdc++.h>
#define N 3005
#define ll long long
using namespace std;
struct A {
    int x, y;
} a[N];
int cmp(int x, int y) {
    return a[x].y < a[y].y;
}
int n, m, c, k, L[N], R[N], cnt[N], id[N], ls[N];
vector<int> q[N];
void del(int x) {
    int kk = x;
    for(int i = 1; i <= k; i ++) {
        ls[i] = x;
        x = L[x];
    }
//    printf("\n");for(int i = k; i >= 1; i --) printf(" %d ", ls[i]); printf("     %d\n", cnt[6]);
//    printf("\n");for(int i = k; i >= 1; i --) printf(" %d ", L[ls[i]]); printf("     %d\n", cnt[6]);
    for(int i = k; i >= 1; i --) {
        int x = ls[i];
        cnt[L[x]] += cnt[x]; cnt[x] = 0;
    } //printf("%d\n\n", cnt[6]);
    x = kk;
    if(R[x]) L[R[x]] = L[x];
    if(L[x]) R[L[x]] = R[x];
}
int main() {
    scanf("%d%d%d%d", &n, &m, &c, &k);
    for(int i = 1; i <= c; i ++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        q[a[i].x].push_back(i);
    }
    ll ans = 0;
    for(int x = 1; x <= n; x ++) {
        int gs = 0;
        for(int i = 1; i <= c; i ++) {
            if(a[i].x >= x) id[++ gs] = i;
        }
        sort(id + 1, id + 1 + gs, cmp);
        
        for(int i = 1; i <= c + 1; i ++) L[i] = R[i] = cnt[i] = 0;
        for(int i = 1; i <= gs; i ++) {
            L[id[i]] = id[i - 1];
            R[id[i]] = id[i + 1];
        }
        L[id[1]] = 0, R[id[gs]] = 0;
        
        int l = 0;
        for(int i = 1; i <= m; i ++) {
            while(l < gs && a[id[l + 1]].y <= i) l ++;
            int x = id[l];
            for(int j = 1; j < k; j ++) x = L[x];
            if(x) cnt[x] ++;
        }
        
        ll s = 0;
        for(int i = 1; i <= gs; i ++) s += 1ll * a[id[i]].y * cnt[id[i]];
        ans += s;
        for(int i = n; i > x; i --) {
            for(int j = 0; j < q[i].size(); j ++) {
                int o = q[i][j];
                for(int t = 1; t <= k; t ++) {
                    s = s - 1ll * cnt[o] * a[o].y + 1ll * cnt[o] * a[L[o]].y;
              //      printf("*%lld %d %d  %d*", s, o, L[o], cnt[6]);
                    o = L[o];
                    if(!o) break; //printf("^");
                }
                del(q[i][j]);
            }
            ans += s;
//            printf("%lld\n", s);
//            for(int j = 1; j <= c; j ++) printf("%d ", cnt[j]); printf("\n");
//            for(int j = 1; j <= c; j ++) printf("%d ", L[j]); printf("\n");
//            for(int j = 1; j <= c; j ++) printf("%d ", R[j]); printf("\n");
        }
    }
    printf("%lld", ans);
    return 0;
}
/*
 10 10 10 4
 7 9
 8 1
 5 7
 6 8
 6 4
 5 8
 4 3
 1 3
 5 1
 6 9

 */