(SPOJ) RPLN - Negative Score [Sparse-Table]

http://www.spoj.com/problems/RPLN/

implement with sparse table

<O(n lg n), O(1)>

//use sparse table
#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 1e5 +6;
const int MAX_P = 18;

int a[MAX_N];
int st[MAX_P][MAX_N];
int lg2[MAX_N];
int pow2[MAX_P];

int main () {
    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 T;
    scanf("%d",&T);
    int cases=0;
    while (T--) {
        int n,q;
        scanf("%d %d",&n,&q);
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            st[0][i] = a[i];
        }
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                int r=j+pow2[i-1];
                if (r>n) r=n;
                st[i][j] = min(st[i-1][j],st[i-1][r]);
            }
        }
        printf("Scenario #%d:\n",++cases);
        while (q--) {
            int l,r;
            scanf("%d %d",&l,&r);
            int dis=(r-l+1);
            printf("%d\n",min(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]));
        }
    }
}

(UVA) 1106 - Machine Works [CDQ分治] [DP斜率優化]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3547

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

//dp[i] = max(dp[j] + r[j] - p[j] + (t[i] - t[j] - 1)*g[j])

typedef long long LL;
typedef __int128 LLL;
const int MAX_N = 1e5 + 6;

struct Mac {
    LL t,p,r,g;
    void input() {
        scanf("%lld %lld %lld %lld",&t,&p,&r,&g);
    }
} mac[MAX_N];

struct Line {
    LLL m,b;
    Line(LL _m,LL _b) {
        m=_m;
        b=_b;
    }
    LLL val(LLL x) {
        return m*x+b;
    }
};

bool operator<(const Mac &m1,const Mac &m2) {
    return m1.t < m2.t;
}

bool operator<(const Line &l1,const Line &l2) {
    return l1.m < l2.m || l1.m==l2.m && l1.b<l2.b;
}

LL dp[MAX_N];

//dp[i] = max(dp[j] + r[j] - p[j] + (t[i] - t[j] + 1)*g[j])

bool check(Line _0,Line _1,Line _2) {
    return (_0.m-_2.m)*(_0.b-_1.b) > (_0.b-_2.b)*(_0.m-_1.m);
}

void do_things(int L,int R) {
    int mid=(L+R)>>1;
    vector<Line> v;
    for (int j=L;mid>=j;j++) {
        if (dp[j] >= mac[j].p) {
            v.push_back(Line(mac[j].g,dp[j]+mac[j].r-mac[j].p+(-mac[j].t-1)*mac[j].g));
        }
    }
    sort(v.begin(),v.end());
    vector<Line> dq;   //use vector as deque XD
    for (Line l:v) {
        while (dq.size()   && dq[dq.size()-1].m == l.m) dq.pop_back();
        while (dq.size()>1 && check(l,dq[dq.size()-1],dq[dq.size()-2])) dq.pop_back();
        dq.push_back(l);
    }
    if (!dq.size()) return;
    int now=0;
    for (int i=mid+1;R>=i;i++) {
        while (now+1<dq.size() && dq[now].val(mac[i].t) < dq[now+1].val(mac[i].t)) now++;
        dp[i] = max(LLL(dp[i]),dq[now].val(mac[i].t));
    }
}

void cdq(int L,int R) {
    if (L==R) return;
    int mid=(L+R)>>1;
    cdq(L,mid);
    do_things(L,R);
    cdq(mid+1,R);
}

int main () {
    int n,c,d;
    int cases=0;
    while (scanf("%d %d %d",&n,&c,&d) != EOF) {
        if (!n && !c && !d) break;
        printf("Case %d: ",++cases);
        for (int i=1;n>=i;i++) {
            mac[i].input();
        }
        memset(dp,0,sizeof(dp));
        mac[0]=Mac{0,0,c,0};
        mac[n+1]=Mac{d+1,0,0,0};
        sort(mac,mac+(n+2));
        cdq(0,n+1);
        printf("%lld\n",dp[n+1]);
    }
}

[TIOJ] 1840 . Coding Days コーディングデイス [動態第K大] [整體二分]

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

法一：

BIT + PST  (Binary Indexed Tree + Persistent Segment Tree)
BIT + 可持久化線段樹
樹狀數組 + 主席樹

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

const int MAX_N = 6e4 + 6;
const int MAX_P = 4e6 + 6;
const int MAX_M = 1e4 + 6;

struct Node {
    static Node mem[MAX_P];
    Node *lc,*rc;
    int sum;
    Node() {
        lc=rc=NULL;
        sum=0;
    }
    void pull() {
        sum = lc->sum + rc->sum;
    }
} Node::mem[MAX_P],*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;
}

Node* getNode(Node* old) {
    Node* node = new(ptr++)Node();
    node->lc=old->lc;
    node->rc=old->rc;
    node->sum=old->sum;
    return node;
}

void modify(Node* node,Node* old,int L,int R,int pos,int val) {
    if (L==R) {
        node->sum += val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid) {
        node->lc=getNode(old->lc);
        modify(node->lc,old->lc,L,mid,pos,val);
    }
    else {
        node->rc=getNode(old->rc);
        modify(node->rc,old->rc,mid+1,R,pos,val);
    }
    node->pull();
    return;
}

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

int a[MAX_N];

Node* root[MAX_N];
Node* bit_root[MAX_N];

int query(Node* L_1tree,Node* Rtree,vector<Node*> bitL_1,vector<Node*> bitR,int L,int R,int k) {
    if (L==R) {
        return L;
    }
    int sumr = Rtree->lc->sum;
    int suml = L_1tree->lc->sum;
    for (auto i:bitL_1) {
        suml += i->lc->sum;
    }
    for (auto i:bitR) {
        sumr += i->lc->sum;
    }
    int mid=(L+R)>>1;
    if (k <= sumr-suml) {
        for (Node* &i:bitL_1) {
            i = i->lc;
        }
        for (Node* &i:bitR) {
            i = i->lc;
        }
        return query(L_1tree->lc,Rtree->lc,bitL_1,bitR,L,mid,k);
    }
    else {
        for (Node* &i:bitL_1) {
            i = i->rc;
        }
        for (Node* &i:bitR) {
            i = i->rc;
        }
        return query(L_1tree->rc,Rtree->rc,bitL_1,bitR,mid+1,R,k-sumr+suml);
    }
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        ptr = Node::mem;
        int n,m;
        scanf("%d %d",&n,&m);
        vector<int> v;
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        for (int i=1;m>=i;i++) {
            q[i].input();
            if (q[i].type == 2) v.push_back(q[i].b);
        }
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end()) - v.begin());
        for (int i=1;n>=i;i++) {
            a[i]=lower_bound(v.begin(),v.end(),a[i]) - v.begin() +1;
        }
        for (int i=1;m>=i;i++) {
            if (q[i].type == 2) q[i].b = lower_bound(v.begin(),v.end(),q[i].b) - v.begin() + 1;
        }
        int nn=v.size();
        root[0] = Build(1,nn);
        for (int i=1;n>=i;i++) {
            root[i] = getNode(root[i-1]);
            modify(root[i],root[i-1],1,nn,a[i],1);
            bit_root[i] = getNode(root[0]);
        }
        for (int j=1;m>=j;j++) {
            if (q[j].type == 3) {
                puts("7122");
            }
            else if (q[j].type==1) {
                int L=q[j].a;
                int R=q[j].b;
                int k=q[j].c;
                vector<Node*> bitL_1,bitR;
                for (int i=R;i>0;i-=(i&(-i))) {
                    bitR.push_back(bit_root[i]);
                }
                for (int i=L-1;i>0;i-=(i&(-i))) {
                    bitL_1.push_back(bit_root[i]);
                }
                int ret=query(root[L-1],root[R],bitL_1,bitR,1,nn,k);
                printf("%d\n",v[ret-1]);
            }
            else if (q[j].type==2) {
                int pos=q[j].a;  //pos
                int val=q[j].b;  //val
                int ori=a[pos];
                for (int i=pos;n>=i;i+=(i&(-i))) {
                    modify(bit_root[i],bit_root[i],1,nn,ori,-1);
                }
                for (int i=pos;n>=i;i+=(i&(-i))) {
                    modify(bit_root[i],bit_root[i],1,nn,val,1);
                }
                a[pos] = q[j].b;
            }
        }
    }
}

法二：

整體二分

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;

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

const int N = 2e5 + 6;

int a[N];

struct Event {
    int time,pos,val,flag;
    Event(int _time,int _pos,int _val,int _flag):time(_time),pos(_pos),val(_val),flag(_flag){}
};

int ans[N];

struct Query {
    int L,R,k,time,id;
    Query(int _L,int _R,int _k,int _time,int _id):L(_L),R(_R),k(_k),time(_time),id(_id){}
};

struct BIT {
    int n;
    int p[N];
    void init(int n) {
        this->n = n;
        for (int i=0;n>=i;++i) p[i]=0;
    }
    void add(int pos,int val) {
        for (int i=pos;n>=i;i+=i&(-i)) {
            p[i] += val;
        }
    }
    int qry(int pos) {
        int ret=0;
        for (int i=pos;i>=1;i-=i&(-i)) {
            ret += p[i];
        }
        return ret;
    }
    int query(int L,int R) {
        return qry(R) - qry(L-1);
    }
} bit;

void split_event(int mid,vector<Event>& e,vector<Event>& le,vector<Event>& re) {
    for (Event ee:e) {
        if (ee.val <= mid) le.push_back(ee);
        else re.push_back(ee);
    }
    vector<Event> ().swap(e);
}

void totBS(int L,int R,vector<Query> q,vector<Event> e) {
    if (L==R) {
        for (Query qq:q) {
            ans[qq.id] = L;
        }
        return;
    }
    int mid=(L+R)>>1;
    vector<Event> le,re;
    split_event(mid,e,le,re);
    vector<Query> lq,rq;
    int eid=-1;
    for (int i=0;SZ(q)>i;i++) {
        Query &qq=q[i];
        while (eid+1 < SZ(le) && le[eid+1].time <= qq.time) {
            bit.add(le[eid+1].pos,le[eid+1].flag);
            eid++;
        }
        int ret=bit.query(qq.L,qq.R);
        if (ret < qq.k) {
            qq.k -= ret;
            rq.push_back(qq);
        }
        else {
            lq.push_back(qq);
        }
    }
    while (eid >= 0) {
        bit.add(le[eid].pos,-le[eid].flag);
        eid--;
    }
    vector<Query> ().swap(q);
    totBS(L,mid,lq,le);
    totBS(mid+1,R,rq,re);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        vector<Query> q;
        vector<Event> e;
        vector<int> v;
        for (int i=1;n>=i;++i) {
            scanf("%d",&a[i]);
            e.push_back(Event(0,i,a[i],1));
            v.push_back(a[i]);
        }
        for (int i=1;m>=i;++i) {
            ans[i] = 0;
            int type;
            scanf("%d",&type);
            if (type == 2) {
                //change
                int pos,val;
                scanf("%d %d",&pos,&val);
                v.push_back(val);
                e.push_back(Event(i,pos,a[pos],-1));
                e.push_back(Event(i,pos,val,1));
                a[pos] = val;
            }
            else if (type == 1) {
                int L,R,k;
                scanf("%d %d %d",&L,&R,&k);
                q.push_back(Query(L,R,k,i,i));
            }
            else if (type == 3) {
                int pos,val;
                scanf("%d %d",&pos,&val);
                ans[i] = -2;
            }
        }
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end()) - v.begin());
        for (Event &ee:e) {
            ee.val = lower_bound(v.begin(),v.end(),ee.val) - v.begin() + 1;
        }
        bit.init(n);
        totBS(1,SZ(v),q,e);
        for (int i=1;m>=i;i++) {
            if (ans[i] != 0) {
                if (ans[i] != -2) printf("%d\n",v[ans[i]-1]);
                else puts("7122");
            }
        }
    }
}

(SPOJ) QTREE - Query on a tree [樹鍊剖分]

http://www.spoj.com/problems/QTREE/

樹鍊剖分

不過在TOJ上面的卻TLE了QQ

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

const int MAX_N = 1e5 +6;
const int MAX_P = 17;

vector<int> edg[MAX_N];
int seg[4*MAX_N];
int val[MAX_N];

void init(int id,int L,int R) {
    if (L==R) {
        seg[id] = val[L];
        return;
    }
    int mid=(L+R)>>1;
    init(id*2,L,mid);
    init(id*2+1,mid+1,R);
    seg[id] = max(seg[id*2],seg[id*2+1]);
    return;
}

void modify(int id,int L,int R,int pos,int val) {
    if (L==R) {
        seg[id] = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid) modify(id*2,L,mid,pos,val);
    else modify(id*2+1,mid+1,R,pos,val);
    seg[id] = max(seg[id*2],seg[id*2+1]);
    return;
}

int 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];
    int mid=(L+R)>>1;
    return max(query(id*2,L,mid,l,r),query(id*2+1,mid+1,R,l,r));
}

struct Edge {
    int a,b,c;
    void input() {
        scanf("%d %d %d",&a,&b,&c);
    }
} edge[MAX_N];

int sz[MAX_N];
bool visit[MAX_N];
int par[MAX_P][MAX_N];

void dfs1(int id,int p) {
    par[0][id] = p;
    sz[id] = 1;
    visit[id] = 1;
    for (auto i:edg[id]) {
        if (!visit[i]) {
            dfs1(i,id);
            sz[id] += sz[i];
        }
    }
}

int tin[MAX_N],tout[MAX_N];
int ttin[MAX_N];
int head[MAX_N];
int stamp1,stamp2;
int depth[MAX_N];

void dfs2(int id,int headd,int cur_depth) {
    ttin[id] = stamp1;
    tin[id] = stamp2;
    stamp1++;
    stamp2++;
    visit[id]=1;
    head[id] = headd;
    depth[id] = cur_depth;
    sort(edg[id].begin(),edg[id].end(),[](int &a,int &b) {
        return sz[a] > sz[b];
    });
    bool flag=false;
    for (auto i:edg[id]) {
        if (!visit[i]) {
            if (!flag) {
                dfs2(i,headd,cur_depth+1);
                flag=1;
            }
            else {
                dfs2(i,i,cur_depth+1);
            }
        }
    }
    tout[id]=stamp2;
    stamp2++;
}

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

int get_real_lca(int x,int y) {
    if (depth[x] > depth[y]) swap(x,y);
    if (is_anc(y,x)) return x;
    for (int i=MAX_P-1;i>=0;i--) {
        if (!is_anc(x,par[i][y])) y=par[i][y];
    }
    return par[0][y];
}

int get_fake_lca(int parent,int son) {
    if (parent == son) return 0;
    for (int i=MAX_P-1;i>=0;i--) {
        if (!is_anc(parent,par[i][son])) {
            son = par[i][son];
        }
    }
    return son;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
        for (int i=1;n>i;i++) {
            edge[i].input();
            edg[edge[i].a].push_back(edge[i].b);
            edg[edge[i].b].push_back(edge[i].a);
        }
        memset(visit,0,sizeof(visit));
        dfs1(1,1);
        memset(visit,0,sizeof(visit));
        stamp1=stamp2=1;
        dfs2(1,1,1);
        for (int i=1;n>i;i++) {
            int &_a=edge[i].a,&_b=edge[i].b,_c=edge[i].c;
            if (ttin[_a] > ttin[_b]) swap(_a,_b);
            val[ttin[_b]] = _c;
        }
        val[1] = 0;
        init(1,1,n);
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                par[i][j] = par[i-1][par[i-1][j]];
            }
        }
        char s[10];
        while (1) {
            getchar();
            scanf("%s",s);
            if (s[0]=='D') {
                //huuray!!!
                break;
            }
            else if (s[0]=='C') {
                int a,b;
                scanf("%d %d",&a,&b);
                modify(1,1,n,ttin[edge[a].b],b);
            }
            else {
                int a,b;
                scanf("%d %d",&a,&b);
                if (depth[a] > depth[b]) swap(a,b);
                int lca=get_real_lca(a,b);
                if (a==b) {
                    puts("0");
                    continue;
                }
                int destination=get_fake_lca(lca,b);
                int ans=0;
                while (depth[destination] <= depth[b]) {
                    if (depth[head[b]] >= depth[destination]) {
                        ans = max(ans,query(1,1,n,ttin[head[b]],ttin[b]));
                        b=head[b];
                        b=par[0][b];
                    }
                    else {
                        ans = max(ans,query(1,1,n,ttin[destination],ttin[b]));
                        break;
                    }
                }
                if (lca != a) {
                    destination = get_fake_lca(lca,a);
                    b=a;
                    while (depth[destination] <= depth[b]) {
                        if (depth[head[b]] >= depth[destination]) {
                            ans = max(ans,query(1,1,n,ttin[head[b]],ttin[b]));
                            b=head[b];
                            b=par[0][b];
                        }
                        else {
                            ans = max(ans,query(1,1,n,ttin[destination],ttin[b]));
                            break;
                        }
                    }
                }
                printf("%d\n",ans);
            }
        }
    }
}