题意：

一个颜色序列，\(a_1, a_2, ...a_i\)表示第i个的颜色，给出每种颜色的美丽度\(w_i\)，定义一段颜色的美丽值为该段颜色的美丽值之和（重复的只计算一次），每次都会修改某个位置的颜色或者查询l到r之间的美丽值。

分析：

带修改莫队：在所有询问中多记录一个时间，每次跳转询问前，处理当前时间（上一次操作所在的时间）到目的时间（本次询问所在时间）中的所有修改操作，如果时间是倒退的，就将值改回来，否则就更改值，并且如果修改的位置不在当前的莫队指针之间就直接修改，否则就先删除再添加。

树套树留坑。

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<string>

#include<algorithm>

#include<ctime>

#include<vector>

#include<queue>

using namespace std;

namespace IO{

    template<typename T>

    inline void read(T &x){

        T i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        x = i * f;

    }

    template<typename T>

    inline void wr(T x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 1e5 + 50, M = 1e5 + 50;

typedef long long ll;

int n, head, tail, cur, cnt[N], m, val[N], S;

int col[N], cc[N],  typ[M], last[M], a[M], b[M];

long long ans[M], now;

struct node{

    int l, r, bl, br, id;

    inline bool operator < (const node &p) const{

        if(bl != p.bl) return bl < p.bl;

        if(br != p.br) return br < p.br;

        return id < p.id;

    }

    node(){}

    node(int bb, int c, int d, int o, int e):l(bb), r(c), bl(d), br(o), id(e){}

}qry[M];

int q;

bool sta[N];

inline void modify(int k, int v){

    if(!sta[k]) col[k] = v;

    else {

        cnt[col[k]]--;

        if(!cnt[col[k]]) now -= val[col[k]];

        col[k] = v;

        cnt[col[k]]++;

        if(!(cnt[col[k]] - 1)) now += val[col[k]];

    }

}

inline void change(int curT, int tarT){

    while(curT < tarT){

        curT++;

        if(typ[curT] == 1) modify(a[curT], b[curT]);

    }

    while(curT > tarT){

        if(typ[curT] == 1) modify(a[curT], last[curT]);

        curT--;

    }

}

inline void go(int l, int r){

    while(tail < r){

        tail++;

        sta[tail] ^= 1;

        cnt[col[tail]]++;

        if(!(cnt[col[tail]] - 1)) now += 1ll*val[col[tail]];

    }

    while(tail > r){

        cnt[col[tail]]--;

        sta[tail] ^= 1;

        if(!cnt[col[tail]]) now -= 1ll*val[col[tail]];

        tail--;

    }

    while(head < l){

        cnt[col[head]]--;

        sta[head] ^= 1;

        if(!cnt[col[head]]) now -= 1ll*val[col[head]];

        head++;

    }

    while(head > l){

        head--;

        sta[head] ^= 1;

        cnt[col[head]]++;

        if(!(cnt[col[head]] - 1)) now += 1ll*val[col[head]];

    }

}

int main(){

    freopen("color.in", "r", stdin);

   // freopen("color.out", "w", stdout);

//    int tt = clock();

    read(n), read(m);

    S = pow(n, 2.1 / 3);

    for(int i = 1; i <= n; i++) read(col[i]), cc[i] = col[i];

    for(int i = 1; i <= n; i++) read(val[i]);

    for(int i = 1; i <= m; i++){

        int x, y;

        read(typ[i]), read(x), read(y);

        a[i] = x, b[i] = y;

        if(typ[i] == 1){

            last[i] = cc[x];

            cc[x] = y;

        }

        else {

            qry[++q] = node(x, y, x / S + (x % S ? 1 : 0), y / S + (y % S ? 1 : 0), i);

        }

    }

    sort(qry + 1, qry + q + 1);

    qry[0].id = 0;

    head = tail = now = 0;

    for(int i = 1; i <= q; i++){

        int l = qry[i].l, r = qry[i].r;

        change(qry[i - 1].id, qry[i].id);

        go(l, r);

        ans[qry[i].id] = now;

    }

    for(int i = 1; i <= m; i++)

        if(typ[i] == 2) wr(ans[i]), putchar('\n');

//    cout<<clock() - tt<<endl;

    return 0;

}

巴特西

NOI模拟颜色 - 带修莫队/树套树

题意：

分析：

code

最新文章

热门文章

巴特西

NOI模拟 颜色 - 带修莫队/树套树

题意：

分析：

code

最新文章

热门文章

NOI模拟颜色 - 带修莫队/树套树