dls的数据结构_习题1

将(i, a[i])当作点，对a[i]这个维度扫描，在i这个维度上面建立扫描线
#include

using namespace std;
const int N = 2e5+10;

array que[N];
array a[N];
// 线段树维护树链剖剖分的dfs序
struct Node{
    int l, r;
    int minn;
}tr[4*N];


void pushup(Node &F, Node L, Node R){
    F.minn = min(L.minn, R.minn);
}

void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r){
    if(l == r){
        // 这里注意要加个id,获得序列上l位置的点的是那个点，然后获得他的权值
        tr[u] = {l, r, 0x3f3f3f3f};
    }
    else{
        tr[u] = {l, r, 0x3f3f3f3f};
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid+1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v){
    
    if(tr[u].l >= x && tr[u].r <= x) {
        tr[u].minn = v;
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u<<1, x, v);
        else if(x > mid) modify(u<<1|1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(l > mid) return query(u<<1|1, l, r);
        else if(r <= mid) return query(u<<1, l, r);
        else{
            Node res;
            Node L = query(u << 1, l, r), R = query(u << 1 | 1, l, r);
            pushup(res, L, R);
            return res;
        }
    }
}

int res[N];
int main(){
    int n, m; cin >> n >> m;
    memset(res, 0x3f, sizeof res);
    for(int i = 1; i <= n; i ++){
        int x; scanf("%d", &x);
        a[i] = {x, i};
    }
    for(int i = 1; i <= m; i ++){
        int l, r, x; scanf("%d %d %d", &l, &r, &x);
        que[i] = {x, l, r, i};
    }
    sort(a + 1, a + 1 + n);
    reverse(a + 1, a + 1 + n);
    sort(que + 1, que + 1 + m);
    reverse(que + 1, que + 1 + m);
    build(1, 1, n);
    int i, j;
    for(i = 1, j = 1; i <= m + 1; i ++){
        while(j <= n && que[j][0] > a[i][0]){
            res[que[j][3]]  = query(1, que[j][1], que[j][2]).minn;
            j ++;
        }        
        if(i == m + 1) break;
        modify(1, a[i][1], a[i][0]);
    }  

    for(int i = 1; i <= m; i ++){
        if(res[i] != 0x3f3f3f3f) printf("%d\n", res[i]);
        else printf("-1\n");
    }

}

f[i][j]：表示前i个元素，分成j段的最小代价
f[i][j] = min(f[k][j - 1] + w(k + 1, i)) k = 1, 2, 3, 4, 
这样来看时间复杂度起码是n^2*k
现在使用数据结构来进行优化
第一个维护枚举j,所以去寻找相邻两个j之间的转移是什么样的
当i变大的时候，前面的f[k][j - 1]是不变的，而后面的w(k + 1, i)变成w(k + 1, i + 1)增加的贡献是可以直接计算
并且上面增加的贡献是上一次a[j]出现的及其之前的w,所以这就是一个区间加法，然后查询f的值是一个区间减法
枚举每一个j的时候，我们上一层计算得到的f初始化线段树

#include

using namespace std;
typedef long long LL;
const int N = 2e5+10, mod = 1e9+7;

// 标签在当前节点已经发生作用了，但是还没有对儿孙发生作用
int f[N];
struct Node{
    int l, r;
    int minn, lazy;
}tr[4*N];

void pushup(Node &Fa, Node &L, Node &R){
    Fa.minn = min(L.minn, R.minn);
}

void pushup(int u){
    pushup(tr[u], tr[u<<1], tr[u<<1|1]);
}

void pushdown(Node &Fa, Node &L, Node &R){
    // 标签融合
    L.lazy += Fa.lazy;
    R.lazy += Fa.lazy;
    // 标签向下传递
    L.minn += Fa.lazy;
    R.minn += Fa.lazy;
    // 标签清空
    Fa.lazy = 0;
}

void pushdown(int u){
    pushdown(tr[u], tr[u<<1], tr[u<<1|1]);
}

void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, f[l], 0};
    }
    else{
        tr[u] = {l, r, 0, 0};
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid+1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int v){
    
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].lazy += v;
        tr[u].minn += v;
    }
    else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u<<1, l, r, v);
        if(r > mid) modify(u<<1|1, l, r, v);
        pushup(u);
    }
}

int query(int u, int l, int r){
    
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].minn;
    else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l > mid) return query(u<<1|1, l, r);
        else if(r <= mid) return query(u<<1, l, r);
        else return min( query(u<<1, l, r), query(u<<1|1, l, r) );
    }
}

int a[N], pre[N], last[N];
int main(){
    int n, k; scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        last[i] = pre[a[i]];
        pre[a[i]] = i; 
    }

    for(int i = 1; i <= n; i ++) f[i] = (1 << 30);
    for(int i = 1; i <= k; i ++){
        build(1, 0, n);
        for(int j = 1; j <= n; j ++){
            // 注意这里需要last[j] - 1
            if(last[j] != 0) modify(1, 0, last[j] - 1, j - last[j]);
            // 因为维护的hj的值，所以这里到j-1就行了，当然写道j也没啥问题好像
            f[j] = query(1, 0, j - 1); 
        }
    }
    cout << f[n] << endl;
}

// 对权值扫描，计算答案
#include

#define left fdafadasd
#define right dasda
using namespace std;
const int N = 5e5+10;
typedef long long LL;
int left[N], right[N], l[N], r[N];
int pos[N];
int main(){
    int n, k; scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i ++){
        int x; scanf("%d", &x);
        pos[x] = i;
    }
    // 这里将左右边界设置成一个值非常地巧妙
    for(int i = 0; i <= n + 1; i ++){
        l[i] = max(0, i - 1);
        r[i] = min(n + 1, i + 1);
    }

    int res = 0;
    LL ans = 0;
    for(int i = 1; i <= n; i ++){
        int x = pos[i];
        left[0] = x;
        for(int j = 1; j <= k; j ++){
            x = l[x];
            left[j] = x;
        }
        x = pos[i];
        right[0] = x;
        for(int j = 1; j <= k; j ++){
            x = r[x];
            right[j] = x;
        }
        x = pos[i];
        // 链表删除某一个节点
        l[r[x]] = l[x];
        r[l[x]] = r[x];
        LL seg = 0;
        // 这里左右移动边界的计算
        for(int j = 1; j <= k; j ++){
            seg += 1ll * (left[j - 1] - left[j]) * (right[k - j + 1] - right[k - j]); 
        }
        ans += seg * i;
    }
    cout << ans << endl;
}

// 一共n次操作，所以序列的总长度是n
// a1 + a2 + a3 .... ak = n
// 所以ai的种类有根号n种
// 然后根据序列的长度再进行一次分块
// 长的序列维护原序列，短的序列维护sum

#include

using namespace std;
const int N = 2e5+10;
typedef long long LL;
vector p[N], large;
const int M = 500;
LL sum[M + 10][M + 10];
int main(){
    int n, q; scanf("%d %d", &n, &q);
    for(int i = 1; i <= q; i ++){
        int op; scanf("%d", &op);
        if(op == 1){
            int x, y; scanf("%d %d", &x, &y);
            int m = p[x].size();
            if(m <= M){
                for(int i = 0; i < m; i ++) sum[m][i] -= p[x][i];
            }
            p[x].push_back(y);
            m ++;
            if(m <= M){
                for(int i = 0; i < m; i ++) sum[m][i] += p[x][i];
            }
            else if(m == M + 1) large.push_back(x);
        }
        else if(op == 2){
            int z; scanf("%d", &z);
            LL res = 0;
            for(int i = 1; i <= M; i ++) res += sum[i][z % i];
            for(auto big : large){
                res += p[big][z % (int)p[big].size()];
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}