(UVA) 12345 - Dynamic len [待修改莫隊]

感謝edisonhello幫忙發現錯字>_<

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=3767&mosmsg=Submission+received+with+ID+19859366

最近太久沒發文了=_=，最近應該會把最近寫的code慢慢放上來！

這題可以使用 待修改莫隊 來解答，複雜度是好的O(N ^ 5/3)

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int MAX_N = 5e4 + 6;
const int MAX_M = 1e6 + 6;

int cnt[MAX_M];
int s[MAX_N];

struct Query {
    int L,R,Lid,Rid,T,id;
    void give_val(int _L,int _R,int _Lid,int _Rid,int _T,int _id) {
        L = _L;
        R = _R;
        Lid = _Lid;
        Rid = _Rid;
        T = _T;
        id = _id;
    }
    bool operator<(const Query &q2) {
        if (Lid != q2.Lid) return Lid < q2.Lid;
        if (Rid != q2.Rid) return Rid < q2.Rid;
        return T < q2.T;
    }
} query[MAX_N];

struct Modify {
    int pos,ori_val,after_val;
    void give_val(int _pos,int _ori_val,int _after_val) {
        pos = _pos;
        ori_val = _ori_val;
        after_val = _after_val;
    }
} modify[MAX_N];

int ans[MAX_N];
int cur_ans;

void add(int x) {
    if (cnt[x] == 0) cur_ans++;
    cnt[x]++;
}

void sub(int x) {
    if (cnt[x] == 1) cur_ans--;
    cnt[x]--;
}

void addTime(int T,int L,int R) {
    if (L <= modify[T].pos && modify[T].pos <= R) {
        sub(s[modify[T].pos]);
        add(modify[T].after_val);
    }
    s[modify[T].pos] = modify[T].after_val;
}

void subTime(int T,int L,int R) {
    if (L <= modify[T].pos && modify[T].pos <= R) {
        sub(s[modify[T].pos]);
        add(modify[T].ori_val);
    }
    s[modify[T].pos] = modify[T].ori_val;
}

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        memset(cnt,0,sizeof(cnt));
        memset(ans,-1,sizeof(ans));
        for (int i=1;n>=i;i++) {
            scanf("%d",&s[i]);
        }
        int T=-1;
        int qid=0;
        int B = pow(max(n,m),2.0/3.0);
        if (B<=0) B=1;
        for (int i=1;m>=i;i++) {
            getchar();
            char c;
            int x,y;
            scanf("%c %d %d",&c,&x,&y);
            if (c=='Q') {
                x++;
                query[++qid].give_val(x,y,x/B,y/B,T,i);
            }
            else {
                x++;
                modify[++T].give_val(x,s[x],y);
                s[x] = y;
            }
        }
        sort(query+1,query+qid+1);
        int L=1,R=0;
        for (int i=1;qid >= i;i++) {
            if (query[i].L > query[i].R) {
                ans[query[i].id] = 0;
                continue;
            }
            while (query[i].R > R) add(s[++R]);
            while (query[i].L < L) add(s[--L]);
            while (query[i].R < R) sub(s[R--]);
            while (query[i].L > L) sub(s[L++]);
            while (query[i].T > T) addTime(++T,L,R);
            while (query[i].T < T) subTime(T--,L,R);
            ans[query[i].id] = cur_ans;
        }
        for (int i=1;m>=i;i++) {
            if (ans[i] != -1) printf("%d\n",ans[i]);
        }
    }
}

或者是也可以用 "BIT 套 可持久化線段樹" (树状数组 + 主席树) 來解

#include <iostream>
#include <stdio.h>
#include <set>
#include <map>
#include <cassert>
#include <cstring>
using namespace std;

const int MAX_N = 1e5 + 6;
const int MAX_M = 3e5 + 6;

struct Node {
    int lc,rc;
    int val;
    void give_val(int _lc,int _rc,int _val) {
        lc=_lc;
        rc=_rc;
        val = _val;
    }
} node[300*MAX_N];

int bit_root[MAX_N],root[MAX_N];
int node_cnt;

int getNode(int id) {
    int ret = ++node_cnt;
    node[ret] = node[id];
    return ret;
}

void pull(int id) {
    node[id].val = node[node[id].lc].val + node[node[id].rc].val;
}

void init(int id,int L,int R) {
    if (L==R) {
        node[id].give_val(0,0,0);
        return;
    }
    node[id].give_val(++node_cnt,++node_cnt,0);
    int mid=(L+R)>>1;
    init(node[id].lc,L,mid);
    init(node[id].rc,mid+1,R);
    return;
}

void modify(int old_id,int new_id,int L,int R,int pos,int val) {
    if (L==R) {
        node[new_id].val += val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid) {
        node[new_id].lc = getNode(node[old_id].lc);
        modify(node[old_id].lc,node[new_id].lc,L,mid,pos,val);
    }
    else {
        node[new_id].rc = getNode(node[old_id].rc);
        modify(node[old_id].rc,node[new_id].rc,mid+1,R,pos,val);
    }
    pull(new_id);
    return;
}

int query(int id,int L,int R,int l,int r) {
    if (l<=L && R<=r) return node[id].val;
    int mid=(L+R)>>1;
    if (mid + 1 > r) return query(node[id].lc,L,mid,l,r);
    else if (l > mid) return query(node[id].rc,mid+1,R,l,r);
    return query(node[id].lc,L,mid,l,r) + query(node[id].rc,mid+1,R,l,r);
}

set<int> st[MAX_M];
int last[MAX_N];
int s[MAX_N];
int n,q;

typedef long long LL;

void modify_bit(int L,int R,int pos,int val) {
    if (L>R) assert(0);
    for (int i=L;n>=i;i+=(i&(-i))) {
        modify(bit_root[i],bit_root[i],1,n,pos,val);
    }
    if (R==n) return;
    for (int i=R+1;n>=i;i+=(i&(-i))) {
        modify(bit_root[i],bit_root[i],1,n,pos,-val);
    }
}

int query_bit(int C,int L,int R) {
    int ret=0;
    for (int i=C;i>0;i-=(i&(-i))){
        ret += query(bit_root[i],1,n,L,R);
    }
    return ret;
}

int main (){
    while (scanf("%d %d",&n,&q) != EOF) {
        node_cnt = 0;
        memset(last,0,sizeof(last));
        for (int i=0;MAX_M>i;i++) {
            st[i].clear();
        }
        node[0].give_val(0,0,0);
        root[0] = ++node_cnt;
        init(root[0],1,n);
        map<int,int> mp;
        for (int i=1;n>=i;i++) {
            bit_root[i] = getNode(root[0]);
        }
        int id=1;
        for (int i=1;n>=i;i++) {
            int x;
            scanf("%d",&x);
            int ret=0;
            auto iter=mp.find(x);
            if (iter == mp.end()) {
                mp.insert(make_pair(x,id));
                ret=id;
                id++;
            }
            else {
                ret=iter->second;
            }
            root[i] = getNode(root[i-1]);
            if (last[ret] == 0) {
                modify(root[i-1],root[i],1,n,i,1);
            }
            else {
                modify(root[i-1],root[i],1,n,i,1);
                modify(root[i],root[i],1,n,last[ret],-1);
            }
            last[ret] = i;
            st[ret].insert(i);
            s[i] = ret;
        }
        int pre_ans=0;
        for (int i=1;q>=i;i++) {
            char a;
            getchar();
            int b,c;
            scanf("%c %d %d",&a,&b,&c);
            if (a=='Q') {
                b++;
                if (b>c) {
                    puts("0");
                    continue;
                }
                pre_ans = query(root[c],1,n,b,c);
                pre_ans += query_bit(c,b,c);
                printf("%d\n",pre_ans);
            }
            else {
                b++;
                if (mp[c] == s[b]) continue;
                int del=s[b];
                auto iter=st[del].find(b);
                int ed = n+1;
                auto iter2=iter;
                ++iter;
                if (iter != st[del].end()) ed = *(iter);
                //b ~ ed - 1
                modify_bit(b,ed-1,b,-1);
                auto iter6 = iter2;
                if (iter2 != st[del].begin()) {
                    int start=*(--iter2);
                    modify_bit(b,ed-1,start,1);
                }
                st[del].erase(st[del].find(b));
                //finish delete
                //now let's add
                int ret=0;
                auto iter3=mp.find(c);
                if (iter3 == mp.end()) {
                    mp.insert(make_pair(c,id));
                    ret=id;
                    id++;
                }
                else if (iter3->second == 0) {
                    mp[c] = id;
                    ret=id;
                    id++;
                }
                else {
                    ret=iter3->second;
                }
                st[ret].insert(b);
                auto iter4 = st[ret].find(b);
                ed = n+1;
                auto iter5 = iter4;
                ++iter4;
                if (iter4 != st[ret].end()) {
                    ed = *(iter4);
                }
                modify_bit(b,ed-1,b,1);
                if (iter5 != st[ret].begin()) {
                    int start = *(--iter5);
                    modify_bit(b,ed-1,start,-1);
                }
                s[b] = ret;
            }
        }
    }
    
}