(Sky OJ) 138. Day 2 PH. 魔貫光殺砲 [5/3莫隊]

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

用treap會TLE喔=_=

用BIT才會AC (常數比較小)

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

typedef pair<int,int> pii;
const int MAX_N = 3e4 + 6;
const int MAX_Q = 3e4 + 6;
const int MAX_M = 3e4 + 6;

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

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

int s[MAX_N];
int t[MAX_N],a[MAX_N],b[MAX_N];

struct BIT {
    static const int MAX_N = 3e4 +6;
    pii a[MAX_N];
    int n;
    void init(int _n) {
        n=_n;
        for (int i=0;n>=i;i++) {
            a[i] = make_pair(0,0);
        }
    }
    void modify(int pos,pii val) {
        for (int i=pos;n>=i;i+=(i&(-i))) {
            a[i] = a[i] + val;
        }
    }
    pii query(int pos) {
        pii ret=make_pair(0,0);
        for (int i=pos;i>0;i-=(i&(-i))) {
            ret = ret + a[i];
        }
        return ret;
    }
    pii queryLR(int L,int R) {
        return query(R) - query(L-1);
    }
} bit;

struct Q {
    int L,R,lid,rid,id,t;
    void give_val(int _L,int _R,int _lid,int _rid,int _id,int _t) {
        L=_L,R=_R,lid=_lid,rid=_rid,id=_id,t=_t;
    }
    bool operator<(const Q &q2) {
        if (lid != q2.lid) return lid<q2.lid;
        if (rid != q2.rid) return rid<q2.rid;
        return t<q2.t;
    }
} q[MAX_Q];

struct Modify {
    int pos,last,next;
    void give_val(int _pos,int _last,int _next) {
        pos=_pos;
        last=_last;
        next=_next;
    }
} modify[MAX_Q];

int cur_ans;
int ans[MAX_Q];

int nn;

void add(int x) {
    pii p=bit.queryLR(x,x);
    if (p.first == 0) {
        cur_ans += bit.queryLR(1,x-1).first+1;
        bit.modify(x,make_pair(1,1));
        cur_ans += bit.queryLR(x+1,nn).second;
    }
    else {
        cur_ans += bit.queryLR(1,x-1).first+1;
        bit.modify(x,make_pair(0,1));
    }
}

void sub(int x) {
    pii p=bit.queryLR(x,x);
    if (p.second == 1) {
        cur_ans -= bit.queryLR(x+1,nn).second;
        bit.modify(x,make_pair(-1,-1));
        cur_ans -= (bit.queryLR(1,x-1).first + 1);
    }
    else {
        cur_ans -= (bit.queryLR(1,x-1).first + 1);
        bit.modify(x,make_pair(0,-1));
    }
}

void addTime(int L,int R,int t) {
    Modify &m=modify[t];
    if (L <= m.pos && m.pos <= R) {
        sub(s[m.pos]);
        add(m.next);
    }
    s[m.pos] = m.next;
}

void subTime(int L,int R,int t) {
    Modify &m=modify[t];
    if (L <= m.pos && m.pos <= R) {
        sub(s[m.pos]);
        add(m.last);
    }
    s[m.pos] = m.last;
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    vector<int> v;
    for (int i=1;n>=i;i++) {
        scanf("%d",&s[i]);
        v.push_back(s[i]);
    }
    for (int i=1;m>=i;i++){
        scanf("%d %d %d",&t[i],&a[i],&b[i]);
        if (t[i] == 1)v.push_back(b[i]);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=1;n>=i;i++) {
        s[i]=lower_bound(v.begin(),v.end(),s[i]) - v.begin() + 1;
    }
    int qq=0;
    int B=pow(max(n,m),2.0/3.0);
    int T=-1;
    for (int i=1;m>=i;i++) {
        if (t[i] == 0) {
            q[++qq].give_val(a[i],b[i],a[i]/B,b[i]/B,i,T);
        }
        else if (t[i] == 1) {
            b[i] = lower_bound(v.begin(),v.end(),b[i]) - v.begin() + 1;
            modify[++T].give_val(a[i],s[a[i]],b[i]);
            s[a[i]] = b[i];
        }
    }
    bit.init(v.size() + 2);
    nn=v.size();
    sort(q+1,q+qq+1);
    int L=1,R=0;
    for (int i=1;qq>=i;i++) {
        while (R < q[i].R) add(s[++R]);
        while (L > q[i].L) add(s[--L]);
        while (R > q[i].R) sub(s[R--]);
        while (L < q[i].L) sub(s[L++]);
        while (T < q[i].t) addTime(L,R,++T);
        while (T > q[i].t) subTime(L,R,T--);
        ans[q[i].id] = cur_ans;
    }
    for (int i=1;m>=i;i++) {
        if (ans[i] != 0) printf("%d\n",ans[i]);
    }
}