(Sky OJ) 129. Day 1 PG. 日月卦長的編輯器

https://pc2.tfcis.org/sky/index.php/problem/view/129/

要想辦法 O(N) 喔~

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

const int MAX_N = 1e6 + 6;

int mx[MAX_N],pre[MAX_N],tag[MAX_N],lc[MAX_N],rc[MAX_N],val[MAX_N];
int ans[MAX_N];

int main () {
    int q;
    scanf("%d",&q);
    int id=1;
//    int sz=0;
    int nowL=0;
    int nowR=0;
    int ans_id = 0;
    while (q--) {
        getchar();
        char c;
        scanf("%c",&c);
        if (c=='I') {
            int x;
            scanf("%d",&x);
            if (nowL==0) {
                rc[id] = nowR;
                lc[id] = nowL;
                pre[id] = x;
                mx[id] = x;
                tag[id] = 0;
                if (nowR != 0) {
                    lc[nowR] = id;
                    tag[nowR] += x;
                    pre[nowR] += x;
                    mx[nowR] = max(mx[nowL],pre[nowR]); 
                }
                nowL = id;
            }
            else {
                rc[id] = nowR;
                lc[id] = nowL;
                rc[nowL] = id;
                assert(tag[nowL] == 0);
                pre[id] = pre[nowL] + x;
                mx[id] = max(mx[nowL],pre[id]);
                tag[id]=0;
                if (nowR != 0) {
                    lc[nowR] = id;
                    tag[nowR] += x;
                    pre[nowR] += x;
                    mx[nowR] = max(mx[id],pre[nowR]); 
                }
                nowL = id;
            }
            ans[++ans_id] = mx[id];
            val[id] = x;
            id++;
        }
        else if (c=='D') {
            if (lc[nowL] != 0)rc[lc[nowL]] = nowR;
            if (nowR == 0) {
                nowL = lc[nowL];
                ans_id--;
                continue;
            }
            lc[nowR] = lc[nowL];
            tag[nowR] -= val[nowL];
            pre[nowR] -= val[nowL];
            nowL = lc[nowL];
            mx[nowR] = max(mx[nowL],pre[nowR]);
            ans_id--;
        }
        else if (c=='R') {
            if (nowR != 0) {
                if (nowL != 0) {
                    tag[nowR] += tag[nowL];
                    pre[nowR] += tag[nowL];
                    mx[nowR] = max(mx[nowL],pre[nowR]);
                    tag[nowL] = 0;    
                }
                nowL = nowR;
                nowR = rc[nowR];
                if (nowL != 0) {
                    tag[nowR] += tag[nowL];
                    pre[nowR] += tag[nowL];
                    mx[nowR] = max(mx[nowL],pre[nowR]);
                    tag[nowL] = 0;    
                }
                ans[++ans_id] = mx[nowL];
            }
        }
        else if (c=='L') {
            if (nowL != 0) {
                nowR = nowL;
                nowL = lc[nowL];
                --ans_id;
            }
        }
        else if (c=='Q'){
            int k;
            scanf("%d",&k);
//            assert(ans_id >= k);
            printf("%d\n",ans[k]);
        }
    }
}

(Sky OJ) 122. 網路流 [Flow]

https://pc2.tfcis.org/sky/index.php/problem/view/122/

Dinic Flow

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct Dinic {
    static const int MAX_N = 306;
    struct Edge {
        int to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,bool type=false) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        if (!type)edg[to].push_back({from,0,SZ(edg[from])-1});
        else edg[to].push_back({from,cap,SZ(edg[from])-1});
    }
    int n,s,t,iter[MAX_N],level[MAX_N];
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
    }
    void bfs() {
        queue<int> que;
        que.push(s);
//        for (int i=0;n>=i;i++) {
//            level[i] = -1;
//        }
        memset(level,-1,sizeof(level));
        level[s]=0;
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (Edge e:edg[t]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[t] +1;
                    que.push(e.to);
                }
            }
        }
    }
    const int INF = 1e9 +7;
    int dfs(int id,int flow) {
        if (id==t) return flow;
        for (int &i=iter[id];SZ(edg[id])>i;i++) {
            Edge &e=edg[id][i];
            if (e.cap > 0 && level[e.to] == level[id] + 1) {
                int d=dfs(e.to,min(flow,e.cap));
                if (d>0) {
                    e.cap -= d;
                    edg[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int flow() {
        int flow=0;
        while (1) {
            bfs();
            if (level[t]==-1) break;
//            for (int i=0;n>=i;i++) iter[i]=0;
            memset(iter,0,sizeof(iter));
            int ret=0;
            while ((ret=dfs(s,INF)) > 0) flow+=ret;
        }
        return flow;
    }
} Flow;

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        Flow.init(n,1,n);
        for (int i=1;m>=i;i++) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            Flow.add_edge(a,b,c,true);
        }
        if (n!=1)printf("%d\n",Flow.flow());
        else puts("0");
    }
}

(Sky OJ) 92. 大榕樹的咒語

https://pc2.tfcis.org/sky/index.php/problem/view/92/

Treap~~

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

#define int long long

const int INF = 1e15 + 7;

struct Val {
    int lmax,rmax,midmax,sum;
    void rev() {
        swap(lmax,rmax);
    }
};

Val operator+(const Val &v1,const Val &v2) {
    Val ret;
    ret.lmax = max(v1.lmax,v1.sum+v2.lmax);
    ret.rmax = max(v2.rmax,v2.sum+v1.rmax);
    ret.midmax = max(max(v1.midmax,v2.midmax),v1.rmax + v2.lmax);
    ret.sum = v1.sum + v2.sum;
    return ret;
}

const int MAX_N = 4500006;

struct Treap {
    static Treap mem[MAX_N];
    Treap *lc,*rc;
    int sz,key,tag,pri;
    bool rev;
    Val val;
    Treap(){
        
    }
    Treap(int _val) : sz(1),key(_val),pri(rand()),tag(INF),rev(0),val({_val,_val,_val,_val}),lc(NULL),rc(NULL) {
        
    }
} Treap::mem[MAX_N],*ptr=Treap::mem;

int Sz(Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    if (!t) return;
    t->sz = 1;
    t->val = {t->key,t->key,t->key,t->key};
    if (t->lc) {
        t->val = t->lc->val +t->val;
        t->sz += t->lc->sz;
    }
    if (t->rc) {
        t->val = t->val + t->rc->val;
        t->sz += t->rc->sz;
    }
}

void push(Treap* t) {
    if (!t) return;
    if (t->rev) {
        if (t->lc) {
            swap(t->lc->lc,t->lc->rc);
            t->lc->rev ^= t->rev;
            t->lc->val.rev();
        }
        if (t->rc) {
            swap(t->rc->lc,t->rc->rc);
            t->rc->rev ^= t->rev;
            t->rc->val.rev();
        }
        t->rev ^= 1;
    }
    if (t->tag == INF) return;
    if (t->lc) {
        t->lc->tag = t->lc->key = t->tag;
        t->lc->val = {max(t->tag,t->lc->sz*t->tag),max(t->tag,t->lc->sz*t->tag),max(t->tag,t->lc->sz*t->tag),t->lc->sz*t->tag};
    }
    if (t->rc) {
        t->rc->tag = t->rc->key = t->tag;
        t->rc->val = {max(t->tag,t->rc->sz*t->tag),max(t->tag,t->rc->sz*t->tag),max(t->tag,t->rc->sz*t->tag),t->rc->sz*t->tag};
    }
    t->tag = INF;
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri) {
        push(a);
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        push(b);
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) {
        a=b=NULL;
        return;
    }
    push(t);
    if (Sz(t->lc) + 1 <= k) {
        a=t;
        split(t->rc,k - Sz(t->lc) - 1,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    srand(time(NULL));
    Treap* root=NULL;
    int n,m;
    cin >> n >> m;
    for (int i=1;n>=i;i++) {
        int x;
        cin >> x;
        root=merge(root,new(++ptr)Treap(x));
    }
    while (m--) {
        string s;
        cin >>s;
        if (s=="MAX-SUM") {
            if (root!=NULL)cout<<root->val.midmax<<'\n';
            else cout<<0<<'\n';
        }
        else if (s=="GET-SUM") {
            int p,k;
            cin >> p >> k;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            if (root != NULL)cout<<root->val.sum<<'\n';
            else cout<<0<<'\n';
            root=merge(merge(tl,root),tr);
        }
        else if (s=="REVERSE") {
            int p,k;
            cin >> p >> k;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            root->rev ^= 1;
            swap(root->lc,root->rc);
            root->val.rev();
            root=merge(tl,merge(root,tr));
        }
        else if (s=="DELETE") {
            int p,k;
            cin >> p >> k;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            root=merge(tl,tr);
        }
        else if (s=="INSERT") {
            int p,k;
            cin >> p >> k;
            Treap* tl;
            split(root,p,tl,root);
            while (k--) {
                int x;
                cin >>x;
                tl=merge(tl,new(++ptr)Treap(x));
            }
            root=merge(tl,root);
        }
        else if (s=="MAKE-SAME") {
            int p,k,l;
            cin >> p >> k >> l;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            root->tag = l;
            root->val = {max(root->tag,root->sz*root->tag),max(root->tag,root->sz*root->tag),max(root->tag,root->sz*root->tag),root->sz*root->tag};
            root->key = root->tag;
            root=merge(tl,merge(root,tr));
        }
    }
}

(Sky OJ) 26. G.雷精靈的煩惱(互動題)

https://pc2.tfcis.org/sky/index.php/problem/view/26/

最naive的做法就是：把每個數值找出來之後，看看不見的是哪一個就okay了！

但是，仔細想想，假設你今天只focus在第一個bit，你會發現，這個bit是0的數字們的數量 跟 這個bit是1的數字們的數量 相差最多是1！從中，你就可以發現不見的bit是0還是1。

那，得到這個之後，我們就不用再檢查所有的數字了！只需要檢查上面找到的兩堆數字中，size比較小的那堆 (可以想想看為甚麼)。

這樣需要的次數就是O(N) + O(N/2) + O(N/4) + ....... = O(2N)

#include <iostream>
#include <stdio.h>
#include <vector>
#include "Pikachu.h"
using namespace std;

int main () {
    int n=Init();
    vector<int> v;
    for (int i=0;n-1>i;i++) v.push_back(i+1);
    int bit=-1;
    int ans=0;
    while (v.size() != 0) {
        bit++;
        vector<int> _[2];
        for (int i:v) {
            if (GetBit(i,bit) == 1) _[1].push_back(i);
            else _[0].push_back(i);
        }
        if (_[0].size() > _[1].size()) {
            v=_[1];
            ans += (1<<bit);
        }
        else {
            v=_[0];
        }
    }
    Answer(ans);
}

(Sky OJ) 2. Maximum Average Submatrix

https://pc2.tfcis.org/sky/index.php/problem/view/2/

這題乍看之下超難的。

不過仔細想想，答案不就是整個矩陣的最大值嗎？

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

int main () {
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    int mx=0;
    for (int i=1;n>=i;i++) {
        for (int j=1;n>=j;j++) {
            int x;
            scanf("%d",&x);
            mx = max(mx,x);
        }
    }
    printf("%d",mx);
    if (k>0) {
        printf(".");
        while (k--) printf("0");
    }
    puts("");
}

(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;
            }
        }
    }
    
}

(TIOJ) 1169 . 氣球博覽會

http://tioj.ck.tp.edu.tw/problems/1169

想法之後再補，先附上寫了316行的code(沒有模板)。(8200字元，破紀錄惹....)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <ctime>
#include <cstdlib>
#include <cassert>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 2e5+6;
const int MAX_M = 4e5+6;
const int INF= 1e9 + 7;

#define Treap Meruru

pii operator+(const pii &p1,const pii &p2) {
    return make_pair(min(p1.first,p2.first),max(p1.second,p2.second));
}

int f(int x) {
    return x;
}

struct Kirino {
    int dis_mx;
    pii range;
    void shootingstars(int val) {
        range=make_pair(val,val);
        dis_mx = -INF;
    }
};

Kirino empty=Kirino{-INF,make_pair(INF,-INF)};

Kirino operator+(Kirino k1,Kirino k2) {
    Kirino kirino;
    kirino.dis_mx = max(f(k1.dis_mx),f(k2.dis_mx ));
    kirino.range = k1.range + k2.range;
    return kirino;
}

struct Meruru {
    Meruru *lc,*rc;
    Kirino kirino;
    int sz;
    int val;
    int r;
    int dis;
    int pri;
    Meruru(int _val) {
        kirino.shootingstars(_val);
        lc=rc=NULL;
        sz=1;
        pri = rand();
        dis=-INF;
        val = _val;
        r=-INF;
    }
};

int Sz(Meruru* m) {
    return m?m->sz:0;
}

Kirino Kiri(Meruru* m) {
    return m?m->kirino:empty;
}

void pull(Meruru* m) {
    if (!m) return;
    m->sz = Sz(m->lc) + Sz(m->rc) + 1;
    m->kirino = Kiri(m->lc) + Kirino{m->dis,make_pair(m->val,m->val)} + Kiri(m->rc);
}

Meruru* merge(Meruru* m1,Meruru *m2) {
    if (!m1 || !m2) return m1?m1:m2;
    else if (m1->pri > m2->pri) {
        m1->rc=merge(m1->rc,m2);
        pull(m1);
        return m1;
    }
    else {
        m2->lc=merge(m1,m2->lc);
        pull(m2);
        return m2;
    }
}

void split_by_val(Meruru *m,int k,Meruru* &m1,Meruru* &m2) {
    if (!m) {
        m1=m2=NULL;
        return;
    }
    else if (m->val <= k) {
        m1=m;
        split_by_val(m->rc,k,m1->rc,m2);
        pull(m1);
    }
    else {
        m2=m;
        split_by_val(m->lc,k,m1,m2->lc);
        pull(m2);
    }
}

void split_by_sz(Meruru *m,int k,Meruru* &m1,Meruru* &m2) {
    if (!m) {
        m1=m2=NULL;
        return;
    }
    else if (Sz(m->lc) + 1 <= k) {
        m1=m;
        split_by_sz(m->rc,k-Sz(m->lc)-1,m1->rc,m2);
        pull(m1);
    }
    else {
        m2=m;
        split_by_sz(m->lc,k,m1,m2->lc);
        pull(m2);
    }
}

int c[MAX_N];

struct Q {
    int type,a,b,c;
    void input() {
        scanf("%d",&type);
        if (type==0) {
            scanf("%d %d",&a,&c);
            a++;
            b=a;
        }
        else {
            scanf("%d %d %d",&a,&b,&c);
            a++;
        }
    }
} q[MAX_N];

Meruru* meruru[MAX_M];

void pp(Meruru* m) {
    if (!m) return;
    pp(m->lc);
    cout<<m->val<<' ';
    pp(m->rc);
}

void haha() {
    for (int i=0;6>i;i++) {
        cout<<"Let us see meruru["<<i<<"] : ";
        pp(meruru[i]);
        cout<<endl;
    }
}

int g(int x) {
    if (x>MAX_M) return -INF;
    else return x;
}

int main () {
    srand(time(NULL));
    int n,qq,kk;
    scanf("%d %d %d",&n,&qq,&kk);
    vector<int> v;
    for (int i=1;n>=i;i++) {
        scanf("%d",&c[i]);
        v.push_back(c[i]);
    }
    for (int i=1;qq>=i;i++) {
        q[i].input();
        v.push_back(q[i].c);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=1;n>=i;i++) {
        c[i] = lower_bound(v.begin(),v.end(),c[i]) - v.begin() + 1;
//        cout<<"c["<<i<<"] = "<<c[i]<<endl;
    }
    for (int i=1;qq>=i;i++) {
        q[i].c = lower_bound(v.begin(),v.end(),q[i].c) - v.begin() + 1;
    }
    int nn=v.size();
    for (int i=1;nn>=i;i++) {
        meruru[i] = NULL;
    }
    for (int i=1;n>=i;i++) {
        int ii=c[i];
        int sz=Sz(meruru[ii]);
//        cout<<"ii = "<<ii<<" , sz = "<<sz<<" , i = "<<i<<endl;
        if (sz == 0) {
            meruru[ii] = new Meruru(i);
//            cout<<"hihi i = "<<i<<endl;
        }
        else {
            Meruru *tl;
            split_by_sz(meruru[ii],sz-1,tl,meruru[ii]);
            meruru[ii]->r = i;
            meruru[ii]->dis = i-meruru[ii]->val;
            meruru[ii] = merge(merge(tl,meruru[ii]),new Meruru(i));
        }
//        cout<<"i = "<<i<<endl;
//        haha();
//        cout<<"after process ii = "<<ii<<" , sz = "<<Sz(meruru[ii])<<" , i = "<<i<<endl;
    }
//    haha();
    for (int i=1;qq>=i;i++) {
//        cout<<"i = "<<i<<" query = "<<"("<<q[i].type<<","<<q[i].a<<","<<q[i].b<<","<<q[i].c<<")"<<endl;
        int type=q[i].type;
        if (type == 0) {
            int p=q[i].a;
            int k=q[i].c;
            //change 
            int ori=c[p];
            if (ori == k) continue;
            c[p] = k;
            //delete first
            Meruru *m1,*m2,*m3;
            split_by_val(meruru[ori],p-1,m1,meruru[ori]);
            if (Sz(m1) == 0) {
//                split_by_sz(meruru[ori],1,m2,meruru[ori]);
                split_by_val(meruru[ori],p,m2,meruru[ori]);
                assert(Sz(m2)==1 && m2->val == p);
                delete(m2);
            }
            else {
                split_by_sz(m1,Sz(m1)-1,m1,m2);  //m2 is the last valid
                split_by_sz(meruru[ori],1,meruru[ori],m3);
                assert(Sz(meruru[ori])==1 && meruru[ori]->val == p);
                m2->r = meruru[ori]->r;
                m2->dis = m2->r-m2->val;
                delete(meruru[ori]);
//                pull(m3);
//                m2->r = g((Kiri(m3)).range.first);
//                m2->dis = f(m2->r-m2->val);
                pull(m2);
                meruru[ori] = merge(m1,merge(m2,m3));
            }
//            cout<<"finish deleting !!!"<<endl;
            //Ooosh... delete finished
            //now let's adding
            Meruru *m4,*m5,*m6;
            if (Sz(meruru[k]) == 0) {
//                cout<<"inn"<<endl;
                meruru[k] = new Meruru(p);
            }
            else {
                split_by_val(meruru[k],p-1,m4,meruru[k]);
                if (Sz(m4)==0) {
//                    cout<<"haha"<<endl;
                    m5 = new Meruru(p);
                    pull(meruru[k]);
                    m5->r = g(Kiri(meruru[k]).range.first);
                    if (m5->r == INF) m5->r=-INF;
                    m5->dis = m5->r - m5->val;
                    pull(m5);
                    meruru[k] = merge(m5,meruru[k]);
                }
                else {
//                    cout<<"hehe"<<endl;
                    split_by_sz(m4,Sz(m4)-1,m4,m5);
                    m6 = new Meruru(p);
                    m6->r=m5->r;
                    m6->dis = m6->r-m6->val;
                    m5->r=p;
                    m5->dis = f(m5->r - m5->val );
//                    cout<<"still_in"<<endl;
//                    pull(meruru[k]);
//                    m6->r = g(Kiri(meruru[k]).range.first);
//                    m6->dis = f(m6->r - m6->val );
                    pull(m5);
                    pull(m6);
                    meruru[k] = merge(merge(m4,m5),merge(m6,meruru[k]));
                }
            }
        }
        else {
//            cout<<"i = "<<i<<" : ";
//            pp(meruru[q[i].c ]);
//            cout<<endl;
            int l=q[i].a,r=q[i].b,c=q[i].c;
            if (Sz(meruru[c]) == 0) {
                printf("%d\n",r-l+1);
            }
            else {
                Meruru *m1,*m2,*m3;
                split_by_val(meruru[c],l-1,m1,m2);
                split_by_val(m2,r,m2,m3);
                if (Sz(m2) == 0 ){
                    printf("%d\n",r-l+1);
                }
                else if (Sz(m2) == 1) {
                    int val = m2->val;
                    printf("%d\n",max(val-l,r-val));
                }
                else {
                    Meruru* m4;
                    split_by_sz(m2,Sz(m2)-1,m2,m4);
                    int ans_mx = m2->kirino.dis_mx-1;
                    pull(m2);
                    ans_mx = max(ans_mx,max(f(m2->kirino.range.first-l),f(r-m4->val) ) );
                    m2 = merge(m2,m4);
                    printf("%d\n",ans_mx);
                }
                meruru[c] = merge(merge(m1,m2),m3);
            }
        }
//        cout<<"i = "<<i<<endl;
//        haha();
    }
}