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

(Zerojudge) b332: NOIP2013 3.小朋友的数字

https://zerojudge.tw/ShowProblem?problemid=b332

有點小小的陷阱QQ

當初我想說，寫一個線段樹求區間連續最大和，開long long，結果一直WA最後兩筆。

仔細想想，最後有可能爆long long!!!!  QQ (想想全部都是10^9的case !!!)

附上悲慘的code：

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

typedef __int128 LL;
const int MAX_N = 1e6 + 6;
const LL INF = 1e17 + 6;

struct Meruru {
    LL sum;
    LL lmax,rmax,midmax;
    void shootingstars(LL _val) {
        sum=lmax=rmax=midmax=_val;
    }
};

Meruru empty={0,-INF,-INF,-INF};

bool operator==(const Meruru &m1,const Meruru &m2) {
    return m1.lmax==m2.lmax && m1.rmax==m2.rmax && m1.midmax==m2.midmax && m1.sum == m2.sum;
}

Meruru pull(Meruru m1,Meruru m2) {
    Meruru meruru;
    if (m1 == empty) return m2;
    if (m2 == empty) return m1;
    meruru.sum = m1.sum+m2.sum;
    meruru.lmax = max(m1.lmax,m1.sum+m2.lmax);
    meruru.rmax = max(m2.rmax,m2.sum+m1.rmax);
    meruru.midmax = max(max(m1.midmax,m2.midmax),m1.rmax+m2.lmax);
    return meruru;
}

struct Node {
    Node *lc,*rc;
    Meruru meruru;
    Node() {
        lc=rc=NULL;
        meruru = empty;
    }
};

LL a[MAX_N];

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        node->meruru.shootingstars(a[L]);
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->meruru = pull(node->lc->meruru,node->rc->meruru);
    return node;
}

Meruru query(Node* node,int L,int R,int l,int r) {
    if (l>R || L>r) return empty;
    else if (l<=L && R<=r) return node->meruru;
    int mid=(L+R)>>1;
    return pull(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

LL p[MAX_N];
LL pp[MAX_N];

int main () {
    int n,mod;
    scanf("%d %d",&n,&mod);
    for (int i=1;n>=i;i++) {
        long long x;
        scanf("%lld",&x);
        a[i]=x;
//        scanf("%lld",&a[i]);
    }
    Node* root=Build(1,n);
    for (int i=1;n>=i;i++) {
        Meruru meruru=query(root,1,n,1,i);
        p[i] = meruru.midmax;
    }
    pp[1] = p[1];
    LL mx=pp[1]+p[1];
    for (int i=2;n>=i;i++) {
        pp[i] = mx;
        mx = max(mx,pp[i] + p[i]);
    }
    mx = pp[1];
    for (int i=1;n>=i;i++) {
        mx = max(mx,pp[i]);
    }
    if (mx<0) {
        printf("%d\n",int(LL(mx)%mod));
    }
    else printf("%d\n",int(mx%mod));
}

(TIOJ) 1171 . 我要成為海賊王 [重心剖分]

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

重心剖分！

說明有空再補吧！

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

typedef long long Meruru;
const int MAX_N = 1e5 + 6;
const int MAX_P = 18;

struct Edge {
    int to,weight;
};

Edge MP(int _to,int _weight) {
    return Edge{_to,_weight};
}

vector<Edge> edg[MAX_N];
Meruru dis[MAX_P][MAX_N];
bool visit[MAX_N];
int sz[MAX_N];
int mx[MAX_N];

struct Cen {
    Meruru minus;
    Meruru val;
    int p;
    int sz;
    int depth;
} cen[MAX_N];

Cen MP_cen(int _p,int _depth) {
    return Cen{0,0,_p,0,_depth};
}

vector<int> v;

void get_cen(int id) {
    visit[id]=1;
    v.push_back(id);
    sz[id]=1;
    mx[id]=0;
    for (Edge i:edg[id]) {
        if (!visit[i.to]) {
            get_cen(i.to);
            mx[id] = max(mx[id],sz[i.to]);
            sz[id] += sz[i.to];
        }
    }
}

void get_dis(int id,int cen_depth,Meruru weight) {
    dis[cen_depth][id] = weight;
    visit[id]=1;
    for (Edge i:edg[id]) {
        if (!visit[i.to]) {
            get_dis(i.to,cen_depth,weight+i.weight);
        }
    }
}

void dfs(int id,int cen_depth,int p) {
    get_cen(id);
    int nn=v.size();
    int ccen=-1;
    for (int i:v) {
        if (max(nn-sz[i],mx[i]) <= nn/2) {
            ccen=i;
        }
        visit[i]=0;
    }
    get_dis(ccen,cen_depth,0);
    for (int i:v) {
        visit[i]=0;
    }
    v.clear();
    visit[ccen]=1;
    cen[ccen] = MP_cen(p,cen_depth);
    for (Edge i:edg[ccen]) {
        if (!visit[i.to]) {
            dfs(i.to,cen_depth+1,ccen);
        }
    }
}

void add(int id) {
    int p=id;
    while (p!=-1) {
        cen[p].val += dis[cen[p].depth][id];
        cen[p].sz++;
        cen[p].minus += dis[cen[p].depth-1][id];
        p=cen[p].p;
    }
}

Meruru query(int id) {
    int p=id;
    Meruru ret=0;
    int szz=0;
    while (p!=-1) {
        ret += (cen[p].val - cen[p].minus);
        ret += (cen[p].sz - szz)*dis[cen[p].depth][id];
        szz = cen[p].sz;
        p=cen[p].p;
    }
    return ret;
}

int main () {
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n>i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        a++;
        b++;
        edg[a].push_back(MP(b,c));
        edg[b].push_back(MP(a,c));
    }
    dfs(1,1,-1);
    memset(visit,0,sizeof(visit));
    while (q--) {
        int a,b;
        scanf("%d %d",&a,&b);
        b++;
        if (a==1 && !visit[b]) {
            add(b);
            visit[b]=1;
        }
        else if (a==2)printf("%lld\n",query(b));
    }
}

(IOICamp_Judge) 導遊讚哥讚！ [重心剖分]

https://judge.ioicamp.org/problems/78

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

#define int long long

typedef long long LL;
const int MAX_N = 1e4 +6;
const int MAX_M = 1e4 +6;
const int MAX_P = 18;

struct Edge {
    int to;
    LL w;
    void _() {
        cout<<"to = "<<to<<" , w = "<<w<<endl;
    }
};

Edge MP(int _to,LL _w) {
    return Edge{_to,_w};
}

vector<Edge> edg[MAX_N];

struct Cen {
    int par;
    LL add;
    LL minus;
    int sz;
    void _() {
        cout<<"par = "<<par<<" , add = "<<add<<" , minus = "<<minus<<" , sz = "<<sz<<endl;
    }
} cen[MAX_N];

int now[MAX_N];
int depth[MAX_N];
Edge lca[MAX_P][MAX_N];
bool visit[MAX_N];
int stamp;
int tin[MAX_N],tout[MAX_N];

void dfs1(int id,int p,LL w,int cur_depth) {
    tin[id] = stamp++;
    visit[id] = 1;
    lca[0][id] = MP(p,w);
    depth[id] = cur_depth;
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs1(i.to,id,i.w,cur_depth+1);
        }
    }
    tout[id] = stamp++;
}

vector<int> v;
int sz[MAX_N];
int mx[MAX_N];

void dfs3(int id) {
    visit[id]=1;
    sz[id]=1;
    mx[id]=0;
    v.push_back(id);
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs3(i.to);
            sz[id] += sz[i.to];
            mx[id] = max(mx[id],sz[i.to]);
        }
    }
}

Cen MP4(int par,LL add,LL minus,int sz) {
    return Cen{par,add,minus,sz};
}

void dfs2(int id,int par_cen) {
    v.clear();
    dfs3(id);
    int can=-1;
    int tot=v.size();
    for (auto i:v) {
        visit[i]=0;
        if (max(mx[i],tot-sz[i]) <= tot/2) {
            can = i;
        }
    }
    visit[can]=true;
    cen[can] = MP4(par_cen,0,0,0);
    for (auto i:edg[can]) {
        if (!visit[i.to]) {
            dfs2(i.to,can);
        }
    }
}

bool is_anc(int son,int parent) {
    return tin[son] >= tin[parent] && tout[son] <= tout[parent];
}

LL get_dis(int x,int y) {
    if (depth[x] > depth[y]) swap(x,y);
    if (x==y) return 0;
    //x is lower
    if(is_anc(y,x)) {
        //we need only from y to x
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
    else {
        int tx=x,ty=y;
        x=tx,y=ty;
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        x=ty,y=tx;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
}

void add(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add += get_dis(now,id);
        cen[now].sz++;
        if (cen[now].par == -1) break;
        cen[now].minus += get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

void deleted(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add -= get_dis(now,id);
        cen[now].sz--;
        if (cen[now].par == -1) break;
        cen[now].minus -= get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

LL query(int id) {
    int now=id;
    LL ret=0;
    int totsz=0;
    while (now != -1) {
        ret += (cen[now].add - cen[now].minus);
        ret += (cen[now].sz - totsz)*get_dis(id,now);
        totsz = cen[now].sz;
        now = cen[now].par;
    }
    return ret;
}

main () {
    int T;
    scanf("%lld",&T);
    while (T--) {
        int n,m,q;
        scanf("%lld %lld %lld",&n,&m,&q);
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
        for (int i=1;n>i;i++) {
            int a,b,c;
            scanf("%lld %lld %lld",&a,&b,&c);
            edg[a].push_back(MP(b,c));
            edg[b].push_back(MP(a,c));
        }
        stamp=0;
        memset(visit,0,sizeof(visit));
        dfs1(1,1,0,1);
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                lca[i][j] = MP(lca[i-1][lca[i-1][j].to].to,lca[i-1][j].w+lca[i-1][lca[i-1][j].to].w);
            }
        }
        memset(visit,0,sizeof(visit));
        dfs2(1,-1);
        now[1]=1;
        for (int i=2;m>=i;i++) {
            add(1);
            now[i]=1;
        }
        while (q--) {
            int a,b;
            scanf("%lld %lld",&a,&b);
            if (a==1) {
                now[a]=b;
            }
            else {
                deleted(now[a]);
                now[a]=b;
                add(now[a]);
            }
            LL ret=query(now[1]);
            printf("%lld\n",ret);
            assert(ret>=0);
        }
    }
}

(TIOJ) 1903 . 【Gate】這個笑容由我來守護 - EXTREME [可刪邊並查集] [時間線段樹] [unodered_map]

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

((解釋有空再補))

#include <iostream>
#include <stdio.h>
#include <utility>
#include <map>
#include <set>
#include <vector>
#include <cassert>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
const LL MAX_N = 5e5 + 6;
namespace std {
  template <> struct hash<pii> {
    LL operator()(const pii &p) const {
      return p.first*MAX_N+p.second;
    }
  };
}

struct Node {
    static Node mem[4*MAX_N];
    Node *lc,*rc;
    vector<pii> v;
    Node() {
        lc=rc=NULL;
        v.clear();
    }
} Node::mem[4*MAX_N],*ptr=Node::mem;

Node* Build(int L,int R) {
    Node* node=new(ptr++)Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int l,int r,pii edge) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        node->v.push_back(edge);
        return;
    }
    int mid=(L+R)>>1;
    modify(node->lc,L,mid,l,r,edge);
    modify(node->rc,mid+1,R,l,r,edge);
}

int ans[MAX_N];

struct Event {
    int tx,ty;
    int ori_sz_tx,ori_sz_ty;
    int ori_p_tx,ori_p_ty;
    pii range;
    void gao(int _tx,int _ty,int _ori_sz_tx,int _ori_sz_ty,int _ori_p_tx,int _ori_p_ty,pii _range) {
        tx=_tx;
        ty=_ty;
        ori_sz_tx=_ori_sz_tx;
        ori_sz_ty=_ori_sz_ty;
        ori_p_tx=_ori_p_tx;
        ori_p_ty=_ori_p_ty;
        range=_range;
    }
};

vector<Event> ee;

struct DisjointSet {
    int p[MAX_N];
    int sz[MAX_N];
    int ans;
    void init(int n) {
        ans=n;
        for (int i=0;n>=i;i++) {
            p[i] = i;
            sz[i]=1;
        }
    }
    int Find(int x) {
        return p[x]==x?x:Find(p[x]);
    }
    void Union(int x,int y,pii range) {
        int tx=Find(x);
        int ty=Find(y);
        if (tx == ty) {
            return;
        }
        if (sz[tx] < sz[ty]) swap(tx,ty);
        assert(sz[tx]>=sz[ty]);
        Event e;
        e.gao(tx,ty,sz[tx],sz[ty],p[tx],p[ty],range);
        ee.push_back(e);
        sz[tx] += sz[ty];
        p[ty] = p[tx];
        ans--;
    }
    void recover(Event e) {
        p[e.tx] = e.ori_p_tx;
        p[e.ty] = e.ori_p_ty;
        sz[e.tx] = e.ori_sz_tx;
        sz[e.ty] = e.ori_sz_ty;
        ans++;
    }
} djs;

void visit(Node* node,int L,int R) {
    //deal with the edges
    pii range=make_pair(L,R);
    for (pii i:node->v) {
        djs.Union(i.first,i.second,range);
    }
    if (L==R) {
        ans[L] = djs.ans;
    }
    else {
        int mid=(L+R)>>1;
        visit(node->lc,L,mid);
        visit(node->rc,mid+1,R);
    }
    while (!ee.empty() && ee.back().range == range) {
        djs.recover(ee.back());
        ee.pop_back();
    }
}

LL hash(pii i) {
    return i.first*MAX_N+i.second;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        ptr=Node::mem;
        int n,m,q;
        scanf("%d %d %d",&n,&m,&q);
        djs.init(n);
        Node* root=Build(1,q+1);
        unordered_map<pii,pii> mp;  //start,count
        for (int i=1;m>=i;i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            if (a>b) swap(a,b);
            pii edge=make_pair(a,b);
            pii ret=mp[edge];
            if (ret == make_pair(0,0)) ret=make_pair(1,1);
            else ret.second++;
            mp[edge]=ret;
        }
        int nn=q+1;
        for (int i=2;q+1>=i;i++) {
            getchar();
            char c;
            int a,b;
            scanf("%c %d %d",&c,&a,&b);
            if (a>b) swap(a,b);
            pii edge=make_pair(a,b);
            if (c=='N') {
                pii ret=mp[edge];
                if (ret == make_pair(0,0)) mp[edge] = make_pair(i,1);
                else {
                    ret.second++;
                    mp[edge]=ret;
                }
            }
            else if (c=='D') {
                pii ret=mp[edge];
                ret.second--;
                if (ret.second==0) {
                    modify(root,1,nn,ret.first,i-1,edge);
                    ret=make_pair(0,0);
                }
                mp[edge]=ret;
            }
        }
        for (auto p:mp) {
            pii edge=p.first;
            pii st=p.second;
            if (st.second==0) continue;
            modify(root,1,nn,st.first,q+1,edge);
        }
        visit(root,1,nn);
        for (int i=2;nn>=i;i++) {
            printf("%d\n",ans[i]);
        }
    }
}

(Zerojudge) b412: 【記憶中】之記憶中的并查集 [可持久化並查集]

https://zerojudge.tw/ShowProblem?problemid=b412

使用黑魔法rope XD

其實可用可持久化線段樹

有啟發式合併 + 路徑壓縮XD

#include <iostream>
#include <stdio.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

const int MAX_N = 1e5 + 6;

rope<int> *p[MAX_N],*sz[MAX_N];
int pp[MAX_N],szz[MAX_N];

int Find(int ver,int x) {
    int ret;
    if (p[ver]->at(x) == x) return x;
    ret = Find(ver,p[ver]->at(x));
    if (p[ver]->at(x) == ret) return ret;
    p[ver]->replace(x,ret);
    return ret;
}

void Union(int ver,int x,int y) {
    x = Find(ver,x);
    y = Find(ver,y);
    if (x==y) return;
    if (sz[ver]->at(x) > sz[ver]->at(y)) {
        sz[ver]->replace(x,(sz[ver]->at(x) + sz[ver]->at(y)));
        p[ver]->replace(y,x);
    }
    else {
        sz[ver]->replace(y,(sz[ver]->at(x) + sz[ver]->at(y)));
        p[ver]->replace(x,y);
    }
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    int ans=0;
    for (int i=0;n>=i;i++) {
        pp[i] = i;
        szz[i] = 1;
    }
    n+=3;
    p[0] = new rope<int>(pp,pp+n+1);
    sz[0]= new rope<int>(szz,szz+n+1);
    for (int i=1;m>=i;i++) {
        int a;
        scanf("%d",&a);
        a^=ans;
        if (a==0) {  //go to history version
            int b;
            scanf("%d",&b);
            b^=ans;
            p[i] = p[b];
            sz[i]=sz[b];
        }
        else if (a==1) {
            int b,c;
            scanf("%d %d",&b,&c);
            p[i] = new rope<int>(*p[i-1]);
            sz[i]= new rope<int>(*sz[i-1]);
            b^=ans;
            c^=ans;
            Union(i,b,c);
        }
        else {
            int b,c;
            scanf("%d %d",&b,&c);
            p[i] = new rope<int>(*p[i-1]);
            sz[i]= new rope<int>(*sz[i-1]);
            b^=ans;
            c^=ans;
            ans = (Find(i,b) == Find(i,c));
            printf("%d\n",ans);
        }
    }
}

(Zerojudge) d539: 區間 MAX [終極sparse-table]

https://zerojudge.tw/ShowProblem?problemid=d539

花O(n lg lg n)預處理，花O(1)查詢任意區間的RMQ。

想法：

把lgN東西分成一塊，對每一塊做Sparse-Table，
總複雜度為O( N/(lgN) * lgN * lg(lgN) ) = O(N lg lg N)

再對每一塊的Max做Sparse-Table : O( (N/lgN) * lg(N/lg(N)) ) = O(N)

之後就可以O(1)查詢。想想看吧！

//use sparse table + magic to <O(n lg lg n),O(1)>
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

const int MAX_N = 5e5 +60;
const int MAX_P = 22;
const int MAX_NN = 19;  //lg N
const int MAX_MM = 5;
const int MAX_NNN = 30000+6;
const int MAX_MMM = 16; //lg NN
const int _INF = -2147483648;

int a[MAX_N];
int st_small[MAX_NNN][MAX_MM][MAX_NN];
int st_big[MAX_MMM][MAX_NNN];
int lg2[MAX_N];
int pow2[MAX_P];

void make_st_small(int n,int *a,int st[MAX_MM][MAX_NN]) {
    for (int i=0;n>i;i++) {
        st[0][i] = a[i];
    }
    for (int i=1;MAX_MM>i;i++) {
        for (int j=0;n>j;j++) {
            int r=j+pow2[i-1];
            if (r>=n) r=n-1;
            st[i][j] = max(st[i-1][j],st[i-1][r]);
        }
    }
}

int query_small(int st[MAX_MM][MAX_NN],int l,int r) {
    int dis=(r-l+1);
    return max(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]);
}

void make_st_big(int n,int *a,int st[MAX_MMM][MAX_NNN]) {
    for (int i=0;n>i;i++) {
        st[0][i] = a[i];
    }
    for (int i=1;MAX_MMM>i;i++) {
        for (int j=0;n>j;j++) {
            int r=j+pow2[i-1];
            if (r>=n) r=n-1;
            st[i][j] = max(st[i-1][j],st[i-1][r]);
        }
    }
}

int query_big(int st[MAX_MMM][MAX_NNN],int l,int r) {
    int dis=(r-l+1);
    return max(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]);
}

void init() {
    pow2[0]=1;
    for (int i=1;MAX_P>i;i++) {
        pow2[i] = pow2[i-1]*2;
    }
    lg2[1] = 0;
    int id=1;
    for (int i=2;MAX_N>i;i++) {
        if (i==pow2[id]) {
            lg2[i] = lg2[i-1]+1;
            id++;
        }
        else {
            lg2[i] = lg2[i-1];
        }
    }
}

int tmp[MAX_NN];
int aa[MAX_NNN];

int main () {
    init();
    int n;
    scanf("%d",&n);
    for (int i=0;n>i;i++) {
        scanf("%d",&a[i]);
    }
    int small_sz=lg2[n];
    if (small_sz<2) small_sz=2;
    int totgroup=n/small_sz + !(n%small_sz==0);
    for (int i=0;totgroup>i;i++) {
        int t=0;
        for (int j=i*small_sz;i*small_sz+small_sz>j;j++) {
            if (j<n) tmp[t++] = a[j];
            else tmp[t++] = _INF;
        }
        make_st_small(small_sz,tmp,st_small[i]);
        aa[i] = query_small(st_small[i],0,small_sz-1);
    }
    make_st_big(totgroup,aa,st_big);
    int q;
    scanf("%d",&q);
    while (q--) {
        int l,r;
        scanf("%d %d",&l,&r);
        if (l>r) swap(l,r);
        l--;
        r--;
        if (l/small_sz == r/small_sz) {
            //in the same group
            int group_first=(l/small_sz)*small_sz;
            printf("%d\n",query_small(st_small[l/small_sz],l-group_first,r-group_first));
            continue;
        }
        int ans=max(query_small(st_small[l/small_sz],l-(l/small_sz)*small_sz,small_sz-1),
        query_small(st_small[r/small_sz],0,r-(r/small_sz)*small_sz));
        if (l/small_sz +1 == r/small_sz) printf("%d\n",ans);
        else printf("%d\n",max(ans,query_big(st_big,l/small_sz+1,r/small_sz-1)));
    }
}

(Zerojudge) d779: NOIP2009 3.最优贸易

https://zerojudge.tw/ShowProblem?problemid=d779

我是先想50%，之後才想到100%的！

在寫50%的時候，我發現圖是一個DAG，用DAG來維護一些東西。

那在推廣到100%的時候，我就在想，要怎麼把整張圖推廣到DAG --> SCC！

50%的版本：

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

const int MAX_N = 1e5 +6;

vector<int> edg[MAX_N];
int a[MAX_N];
int mn[MAX_N];
int mxans[MAX_N];
int deg[MAX_N];

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
        mn[i] = a[i];
        mxans[i]=0;
    }
    for (int i=0;m>i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if (c==1) edg[a].push_back(b);
        else {
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        deg[b]++;
    }
    int ans=0;
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        mxans[t] = max(mxans[t],a[t]-mn[t]);
        for (int i:edg[t]) {
            mn[i] = min(mn[i],mn[t]);
            deg[i]--;
            mxans[i] = max(mxans[i],mxans[t]);
            if (deg[i]==0) que.push(i);
        }
    }
    printf("%d\n",mxans[n]);
}

100%的版本：

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

const int MAX_N = 1e5 + 6;
const int INF = 1e9 + 7;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
vector<int> scc_edg[MAX_N];
int scc_mx[MAX_N],scc_mn[MAX_N],scc_ans[MAX_N];
int a[MAX_N];
bool visit[MAX_N];
int get_stamp[MAX_N];
int in_scc[MAX_N];
int ansmx[MAX_N];
int deg[MAX_N];

void gao1(int id,int &stamp) {
    visit[id]=1;
    for (int i:rev_edg[id]) {
        if (!visit[i]) {
            gao1(i,stamp);
        }
    }
    get_stamp[stamp++]=id;
}

void gao2(int id,int scc) {
    visit[id]=1;
    for (int i:edg[id]) {
        if (!visit[i]) {
            gao2(i,scc);
        }
    }
    in_scc[id]=scc;
    scc_mx[scc] = max(scc_mx[scc],a[id]);
    scc_mn[scc] = min(scc_mn[scc],a[id]);
}

int build_scc(int n) {
    memset(visit,0,sizeof(visit));
    int stamp=1;
    for (int i=1;n>=i;i++) {
        if (!visit[i]) {
            gao1(i,stamp);
        }
    }
    fill(scc_mx,scc_mx+MAX_N,-INF);
    fill(scc_mn,scc_mn+MAX_N,INF);
    memset(visit,0,sizeof(visit));
    int scc=0;
    for (int i=n;i>=1;i--) {
        if (!visit[get_stamp[i]]) {
            gao2(get_stamp[i],++scc);
        }
    }
    for (int i=1;n>=i;i++) {
        for (int j:edg[i]) {
            if (in_scc[i] != in_scc[j]) {
//                cout<<"build edge i = "<<in_scc[i]<<" , j = "<<in_scc[j]<<endl;
                scc_edg[in_scc[i]].push_back(in_scc[j]);
            }
        }
    }
    return scc;
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
    }
    for (int i=1;m>=i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        edg[a].push_back(b);
        rev_edg[b].push_back(a);
        if (c==2) {
            edg[b].push_back(a);
            rev_edg[a].push_back(b);
        }
    }
    int scc=build_scc(n);
//    cout<<"scc = "<<scc<<endl;
//    for (int i=1;n>=i;i++) {
//        cout<<"in_scc["<<i<<"] = "<<in_scc[i]<<endl;
//    }
    queue<int> que;
    for (int i=1;scc>=i;i++) {
        for (int j:scc_edg[i]) {
            deg[j]++;
        }
    }
    que.push(in_scc[1]);
    while (!que.empty()) {
        int t=que.front();
//        cout<<"T = "<<t<<endl;
        que.pop();
        ansmx[t] = max(ansmx[t],scc_mx[t]-scc_mn[t]);
        for (int i:scc_edg[t]) {
            deg[i]--;
            scc_mn[i] = min(scc_mn[i],scc_mn[t]);
            ansmx[i] = max(ansmx[i],ansmx[t]);
            if (deg[i] == 0) que.push(i);
        }
    }
    printf("%d\n",ansmx[in_scc[n]]);
}