yp155136 coding area: Sky OJ

顯示具有 Sky OJ 標籤的文章。顯示所有文章

2017年8月18日星期五

(Sky OJ) 154. DAY 4 PH. 字串雜湊

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

很奇怪的min cut XD

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

typedef long long LL;

struct Dinic {
    static const int MAX_N = 4e4 + 6;
    struct Edge {
        LL to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    int n,s,t;
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n+1>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N],level[MAX_N];
    void BFS() {
        queue<int> que;
        memset(level,-1,sizeof(level));
        level[s] = 0;
        que.push(s);
        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);
                }
            }
        }
    }
    LL dfs(int id,LL 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 ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const LL INF = 1e15 + 7;
    LL flow() {
        LL ret=0;
        while (1) {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            LL tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

typedef long long LL;
typedef vector<LL> vint;
const int MAX_N = 106;
const LL mod = 71234;
const LL INF = 1e9 +7;
int v[144];

vint dp[MAX_N];
vint mn[MAX_N];
vint edg[MAX_N];
int deg[MAX_N];
bool visit[MAX_N];
#define SZ(x) ((int)(x).size())
vint dp2[MAX_N];
int ppre[MAX_N];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >>n >>m;
    for (int i='a';'z'>=i;i++) {
        cin >>v[i];
    }
    for (int i=1;n>=i;i++) {
        dp[i].push_back(INF);
        string s;
        cin >> s;
        LL pre=0;
        int sz=0;
        for (int j=0;s.size()>j;j++) {
            pre *= (j);
            pre += v[s[j]];
            pre %= mod;
            if (SZ(s) % (j+1) == 0) {
                dp[i].push_back(pre);
                sz++;
            }
        }
        ppre[i] = ppre[i-1] + sz;
    }
    int s=0,t=ppre[n] + 1;
    dinic.init(t,s,t);
    for (int i=1;n>=i;i++) {
        int first=ppre[i-1];
        dinic.add_edge(s,first+1,INF);
        for (int j=1;SZ(dp[i])>j;j++) {
            if (j==SZ(dp[i]) - 1) dinic.add_edge(first+j,t,dp[i][j]);
            else dinic.add_edge(first+j,first+j+1,dp[i][j]);
        }
    }
    for (int i=1;m>=i;i++) {
        int x,y;
        cin >> x >> y;
        int firstx=ppre[x-1],firsty=ppre[y-1];
        for (int j=1;min(SZ(dp[x]),SZ(dp[y])) > j;j++) {
            dinic.add_edge(firstx+j,firsty+j,INF);
        }
    }
    cout<<dinic.flow()<<'\n';
}

(Sky OJ) 153. Day 4 PG. Hard Game [二分圖]

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

警告：本份code的解法非官方正解，而且是用了壓常數的方法過的

本題要得答案是 (n - 最大匹配必經點) ，那，若一個點是"最大匹配必經點"，這個點就找不到增廣路徑了！

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

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

vector<short> edg[MAX_N];
int col[MAX_N];
int match[MAX_N];
bool visit[MAX_N];
bool can[MAX_N];

int limitid,limiti;

bool dfs2(short id) {
    if (id == -1) return true;
    if(id == limitid) return false;
    for (short i:edg[id]) {
        if (visit[i]) continue;
        visit[i]=1;
        if (match[i] == -1 || match[i] != limitid && dfs2(match[i])) {
            return true;
        }
    }
    return false;
}

typedef int LL;

#define short unsigned short

struct Dinic {
    static const short MAX_N = 2e4 + 6;
    struct Edge {
        short to,cap;
        int rev;
    };
    vector<Edge> edg[MAX_N];
    short n,s,t;
    void init(short _n,short _s,short _t) {
        n=_n;
        s=_s;
        t=_t;
        for (short i=0;n+1>=i;++i) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(short from,short to,short cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N];
    short level[MAX_N];
    void BFS() {
        queue<short> que;
        memset(level,0,sizeof(level));
        level[s] = 1;
        que.push(s);
        while (!que.empty()) {
            short t=que.front();
            que.pop();
            for (Edge &e:edg[t]) {
                if (e.cap > 0 && level[e.to] == 0) {
                    level[e.to] = level[t] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    short dfs(short id,short 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) {
                short ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const short INF = 60000 + 7;
    short flow() {
        short ret=0;
        while (1) {
            BFS();
            if (level[t] == 0) break;
            memset(iter,0,sizeof(iter));
            short tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    int s=0,t=2*n+1;
    dinic.init(t,s,t);
    for (int i=1;m>=i;++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        dinic.add_edge(a,b+n,1);
        dinic.add_edge(b,a+n,1);
        edg[a].push_back(b);
        edg[b].push_back(a);
    }
    for (int i=1;n>=i;++i) {
        dinic.add_edge(s,i,1);
    }
    for (int i=1;n>=i;++i) {
        dinic.add_edge(i+n,t,1);
    }
    int ans=0;
    dinic.flow();
    memset(match,-1,sizeof(match));
    for (int i=1;n>=i;++i) {
        for (auto e:dinic.edg[i]) {
            if (e.to > i && e.cap == 0) {
                match[e.to-n] = i;
            } 
        }
    }
    for (int i=1;n>=i;++i) {
        if (match[i] == -1) ++ans;
        else {
            memset(visit,0,sizeof(visit));
            if(dfs2(match[i])) ++ans;
        }
    }
    printf("%d\n",ans);
}

(Sky OJ) 151. Day 4 PC. 西西瓦賽跑

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

Dinic Flow

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

typedef long long LL;

struct Dinic {
    static const int MAX_N = 4e4 + 6;
    struct Edge {
        LL to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    int n,s,t;
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n+1>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N],level[MAX_N];
    void BFS() {
        queue<int> que;
        memset(level,-1,sizeof(level));
        level[s] = 0;
        que.push(s);
        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);
                }
            }
        }
    }
    LL dfs(int id,LL 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 ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const LL INF = 1e15 + 7;
    LL flow() {
        LL ret=0;
        while (1) {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            LL tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

const int MAX_R = 1e3 + 6;
const int MAX_K = 26;

int x[MAX_R][MAX_K];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int r,k,l;
        scanf("%d %d %d",&r,&k,&l);
        int s=2*r*k,t=2*r*k+1;
        dinic.init(t,s,t);
        int n=r*k;
        for (int i=0;r>i;i++) {
            for (int j=0;k>j;j++) {
                scanf("%d",&x[i][j]);
                //i * k + j
                if (i==0) {
                    dinic.add_edge(s,i*k+j,1);
                }
                if (i==r-1) {
                    dinic.add_edge(i*k+j+n,t,1);
                }
                dinic.add_edge(i*k+j,i*k+j+n,1);
                if (i>0) {
                    for (int kk=0;k>kk;kk++) {
                        if (abs(x[i][j] - x[i-1][kk]) <= l) dinic.add_edge((i-1)*k+kk+n,i*k+j,1);
                    }
                }
            }
        }
        printf("%d\n",dinic.flow());
    }
}

(Sky OJ) 146. Day 3 PH. 樹樹鏈鏈剖剖分分 [樹鏈剖分]

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

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

typedef long long LL;
const int MAX_N = 2e5 +6;
const int MAX_P = 19;

vector<int> edg[MAX_N];
int depth[MAX_N];
int p[MAX_N];
int lca[MAX_P][MAX_N];
int pin[MAX_N],pout[MAX_N];
int sz[MAX_N];
int stamp;

void dfs(int id,int p,int cur_depth) {
    lca[0][id] = p;
    depth[id] = cur_depth;
    pin[id] = stamp++;
    sz[id] = 1;
    for (int i:edg[id])  {
        if (i!=p) {
            dfs(i,id,cur_depth+1);
            sz[id] += sz[i];
        }
    }
    pout[id] = stamp++;
}

bool is_anc(int parent,int son ){
    return pin[parent] <= pin[son] && pout[son] <= pout[parent];
}

int get_lca(int a,int b) {
    if (depth[a] > depth[b]) swap(a,b);
    if (is_anc(a,b)) return a;
    int bb=b;
    for (int i=MAX_P-1;i>=0;i--) {
        if (!is_anc(lca[i][b],a)) b=lca[i][b];
    }
    b=lca[0][b];
    return b;
}

LL seg[4*MAX_N];
int tag[4*MAX_N];

void push(int id,int L,int R) {
    if (L==R) tag[id]=0;
    if (tag[id]==0) return;
    tag[id*2] += tag[id];
    tag[id*2+1] += tag[id];
    int mid=(L+R)>>1;
    seg[id*2] += tag[id]*(mid-L+1);
    seg[id*2+1] += tag[id]*(R-mid);
    tag[id]=0;
    return;
}

void modify(int id,int L,int R,int l,int r,int val) {
    if (l>R || L>r) return;
    else if (l<=L && R<=r) {
        tag[id] += val;
        seg[id] += (R-L+1)*val;
        return;
    }
    push(id,L,R);
    int mid=(L+R)>>1;
    if (mid + 1 > r) modify(id*2,L,mid,l,r,val);
    else if (l > mid) modify(id*2+1,mid+1,R,l,r,val);
    else {
        modify(id*2,L,mid,l,r,val);
        modify(id*2+1,mid+1,R,l,r,val);
    }
    seg[id] = seg[id*2] + seg[id*2+1];
}

LL query(int id,int L,int R,int l,int r){
    if (l>R || L>r) return 0;
    else if (l<=L && R<=r) return seg[id];
    push(id,L,R);
    int mid=(L+R)>>1;
    if (mid + 1 > r) return query(id*2,L,mid,l,r);
    else if (l > mid) return query(id*2+1,mid+1,R,l,r);
    else {
        return query(id*2,L,mid,l,r) + query(id*2+1,mid+1,R,l,r);
    }
}

#define SZ(x) ((int)(x).size())

int head[MAX_N];
int tin[MAX_N];

int n,m;

void dfs2(int id,int p,bool nnew) {
    sort(edg[id].begin(),edg[id].end(),[](const int &a,const int &b) {
        return sz[a] >sz[b];
    });
    if (nnew) {
        head[id] = id;
    }
    else {
        head[id] = head[p];
    }
    tin[id] = ++stamp;
    bool gett=false;
    for (int ii=0;SZ(edg[id])>ii;ii++) {
        int i=edg[id][ii];
        if (i==p) continue;
        dfs2(i,id,gett);
        gett=true;
    }
}

LL Q(int son,int parent) {
    if (son == parent) return 0;
    LL ret=0;
    while (head[son] != head[parent]) {
        //son --> head[son]
        ret += query(1,1,n,tin[head[son]],tin[son]);
        son = head[son];
        son = lca[0][son];
    }
    if (son == parent) return ret+0;
    else return ret+query(1,1,n,tin[parent]+1,tin[son]);
}

void change(int son,int parent) {
    if (son == parent) return;
    while (head[son] != head[parent]) {
        //son --> head[son]
        modify(1,1,n,tin[head[son]],tin[son],1);
        son = head[son];
        son = lca[0][son];
    }
    if (son == parent) return;
    else modify(1,1,n,tin[parent]+1,tin[son],1);
}

int main () {
    scanf("%d %d",&n,&m);
    for (int i=1;n>i;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        edg[a].push_back(b);
        edg[b].push_back(a);
    }
    stamp=0;
    dfs(1,1,1);
    for (int i=1;MAX_P>i;i++) {
        for (int j=1;n>=j;j++) {
            lca[i][j] = lca[i-1][lca[i-1][j]];
        }
    }
    stamp=0;
    dfs2(1,1,1);
    for (int i=1;m>=i;i++) {
        getchar();
        char c;
        int a,b;
        scanf("%c %d %d",&c,&a,&b);
        int lca = get_lca(a,b);
        if (c=='P') {
            change(a,lca);
            change(b,lca);
        }
        else if (c=='Q') {
            printf("%lld\n",Q(a,lca) + Q(b,lca));
        }
    }
}

(Sky OJ) 145. Day 3 PG. 卦長的背包 [LCA]

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

LCA

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

typedef long long LL;
const int MAX_N = 2e5 + 6;
const int MAX_P = 19;

vector<int> edg[MAX_N];
int depth[MAX_N];
int p[MAX_N];
int lca[MAX_P][MAX_N];
int pin[MAX_N],pout[MAX_N];
int stamp;

void dfs(int id,int p,int cur_depth) {
    lca[0][id] = p;
    depth[id] = cur_depth;
    pin[id] = stamp++;
    for (int i:edg[id]) dfs(i,id,cur_depth+1);
    pout[id] = stamp++;
}

bool is_anc(int parent,int son ){
    return pin[parent] <= pin[son] && pout[son] <= pout[parent];
}

int query(int a,int b) {
    if (depth[a] > depth[b]) swap(a,b);
    if (is_anc(a,b)) return depth[b] - depth[a];
    int bb=b;
    for (int i=MAX_P-1;i>=0;i--) {
        if (!is_anc(lca[i][b],a)) b=lca[i][b];
    }
    b=lca[0][b];
    swap(b,bb);
    return depth[a] + depth[b] - depth[bb]*2;
}

int main () {
    int n;
    scanf("%d",&n);
    for (int i=2;n>=i;i++) {
        int p;
        scanf("%d",&p);
        edg[p].push_back(i);
    }
    stamp=0;
    dfs(1,1,1);
    for (int i=1;MAX_P>i;i++) {
        for (int j=1;n>=j;j++) {
            lca[i][j] = lca[i-1][lca[i-1][j]];
        }
    }
    queue<int> que;
    int last=1;
    que.push(1);
    LL ans=0;
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        ans += query(last,t);
        last=t;
        for (int i:edg[t]) que.push(i);
    }
    printf("%lld\n",ans);
}

(Sky OJ) 144. Day 3 PF. 宿命的對決

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

DP or BFS

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

const int MAX_N = 1e5 + 6;

int dp[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        memset(dp,-1,sizeof(dp));
        int a,b;
        scanf("%d %d",&a,&b);
        if (a==b || a>=b) {
            printf("%lld\n",a-b+1);
            continue;
        }
        dp[a] = 0;
        queue<int> que;
        que.push(a);
        int dx[3] = {1,1,2};
        int dy[3] = {1,-1,0};
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (int i=0;3>i;i++) {
                int tt=t*dx[i]+dy[i];
                if (tt>b) {
                    if (dp[b]==-1) dp[b] = dp[t] + abs(b-tt)+1;
                    else {
                        dp[b] = min(dp[b],dp[t] + abs(b-tt)+1);
                    }
                }
                else if (tt <= 0) ;
                else if (dp[tt] == -1 || dp[tt]>dp[t]) {
                    dp[tt] = dp[t] + 1;
                    que.push(tt);
                }
            }
        }
        printf("%d\n",dp[b]+1);
    }
}

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

(Sky OJ) 137. Day 2 PG. 我愛斯大林 [BIT套可持久化線段樹]

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

BIT + 可持久化線段樹

#include <iostream>
#include <stdio.h>
#include <set>
#include <map>
#include <cassert>
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[530*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) {
    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 (){
    int k,m;
    scanf("%d %d %d %d",&n,&q,&m,&k);
    node_cnt = 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++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if (a==0) {
            b++;
            c++;
            pre_ans = query(root[c],1,n,b,c);
            pre_ans += query_bit(c,b,c);
            printf("%d\n",pre_ans);
        }
        else {
            b++;
            c = (LL(pre_ans)*c%m)*k;
            if (mp[c] == s[b]) continue;
            int del=s[b];
            auto iter=st[del].find(b);
            int ed = n+1;
            ++iter;
            if (iter != st[del].end()) ed = *(iter);
            //b ~ ed - 1
            modify_bit(b,ed-1,b,-1);
            iter--;
            if (iter != st[del].begin()) {
                int start=*(--iter);
                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;
            }
            auto iter4 = st[ret].insert(b).first;
            ed = n+1;
            ++iter4;
            if (iter4 != st[ret].end()) {
                ed = *(iter4);
            }
            --iter4;
            modify_bit(b,ed-1,b,1);
            if (iter4 != st[ret].begin()) {
                int start = *(--iter4);
                modify_bit(b,ed-1,start,-1);
            }
            s[b] = ret;
            st[ret].insert(b);
        }
    }
}

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

訂閱：文章 (Atom)

2017年8月18日 星期五

2017年8月18日星期五