杂题专练(三)

前言

猛然发现前两个杂题训练的英文名都写的’vary’…震惊。
所以? …..懒得改了就这样苟且吧……

BZOJ 3166

题目大意:给一个序列A, 保证A中元素各不相同。定义一个区间[l, r]的价值为区间次大值与区间内任意元素异或的最大值。问所有区间价值最大值。

解题报告

思想比较简单, 首先对于区间次大值为l的区间, 肯定区间越大越好。容易发现一个元素只可能成为两个极大区间的次大值。为了找出这两个区间需要在可持久化线段树上二分。找出这两个区间后再可持久化Trie上贪心就可以了。
现在题目感觉堆代码的一次码不对…思维有高度的都想不出…我差不多就是个废人了

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 50050;
namespace PTrie {
    const int MAXD = MAXN*33;
    struct Node {
        int ch[2], tim;
    } d[MAXD];
    int dtot, tim;
    int roots[MAXN], tot;
    inline void insert (int val) {
        int u = roots[++tot] = ++dtot;
        d[u].tim = ++tim;
        int r = roots[tot-1];
        for(int i = 30; i>=0; i--) {
            bool f = val&(1<<i);
            d[u].ch[!f] = d[r].ch[!f];
            u = d[u].ch[f] = ++dtot;
            d[u].tim = tim;
            r = d[r].ch[f];
        }
    }
    int curL;
    inline int query (int u, int val) {
        int ret = 0;
        for(int i = 30; i>=0; i--) {
            bool f = !(val&(1<<i));
            if(d[d[u].ch[f]].tim >= curL) {
                u = d[u].ch[f];
                if(f) ret |= (1<<i);
            } else {
                u = d[u].ch[!f];
                if(!f) ret |= (1<<i);
            }
        }
        return ret;
    }
}
int N;
namespace PST {
    const int MAXD = MAXN*22;
    int sum[MAXD], lc[MAXD], rc[MAXD], dtot;
    int roots[MAXN], tot;
    int insp;
    void insert (int&u, int lb, int rb, int r) {
        if(lb > insp || rb < insp) {u = r; return ;}
        sum[u = ++dtot] = sum[r]+1;
        if(lb == rb) return ;
        int mid = (lb+rb)>>1;
        insert(lc[u], lb, mid, lc[r]);
        insert(rc[u], mid+1, rb, rc[r]);
    }
    int ql, qr;
    int query (int u1, int u2, int lb, int rb) {
        if(u1 == u2 || ql > rb || qr < lb) return 0;
        if(ql <= lb && rb <= qr) return sum[u2]-sum[u1];
        int mid = (lb+rb)>>1;
        return query(lc[u1], lc[u2], lb, mid)+query(rc[u1], rc[u2], mid+1, rb);
    }
    int handleQuery (int pos, int val, int lim) {
        int lb = 1, rb = pos-1, ans = 0;
        ql = val+1, qr = N;
        //printf("pos:%d, val:%d, lim:%d\n", pos, val, lim);
        while(lb <= rb) {
            int mid = (lb+rb)>>1;
            //printf("q:[%d, %d], ", mid, pos-1);
            int cur = query(roots[mid-1], roots[pos-1], 1, N);
            if(cur >= lim) lb = mid+1;
            else rb = mid-1;
            if(cur == lim) ans = mid;
            //printf("result:%d\n", cur);
        }

        return ans;
    }
    inline void handleInsert (int val) {
        tot ++, insp = val;
        insert(roots[tot], 1, N, roots[tot-1]);
    }
    inline void clear () {
        memset(lc, 0, (dtot+5)*4);
        memset(rc, 0, (dtot+5)*4);
        memset(roots, 0, sizeof roots);
        dtot = 0, tot = 0;
    }
}
int A[MAXN];
int lef[MAXN], rig[MAXN];
int lef2[MAXN], rig2[MAXN];
int ans = 0;
void updateAnswer (int lb, int rb, int val) {
    PTrie::curL = lb;
    int cur = PTrie::query(PTrie::roots[rb], val);
    ans = max(ans, val^cur);
}
int linr[MAXN], img[MAXN];
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%d", &A[i]), linr[i] = A[i];
    std::sort(linr+1, linr+N+1);
    for(int i = 1; i<=N; i++)
        PST::handleInsert(img[i] = lower_bound(linr+1, linr+N+1, A[i])-linr);
    for(int i = 1; i<=N; i++) {
        lef[i] = PST::handleQuery(i, img[i], 1);
        if(lef[i]) lef2[i] = PST::handleQuery(i, img[i], 2);
    }
    PST::clear();
    for(int i = 1; i<=N; i++)
        PST::handleInsert(img[N-i+1]);
    for(int i = 1; i<=N; i++) {
        rig[i] = N-PST::handleQuery(N-i+1, img[i], 1)+1;
        if(rig[i] != N+1)
            rig2[i] = N-PST::handleQuery(N-i+1, img[i], 2)+1;
        else rig2[i] = N+1;
    }
    for(int i = 1; i<=N; i++)
        PTrie::insert(A[i]);
    for(int i = 1; i<=N; i++) {
        if(lef[i] != 0) updateAnswer(lef2[i]+1, rig[i]-1, A[i]);
        if(rig[i] != N+1) updateAnswer(lef[i]+1, rig2[i]-1, A[i]);
    }
    printf("%d\n", ans);
}
/*
5
9 2 1 4 7
*/

BZOJ 2741

题目大意: 给你一个序列, 询问区间子串异或和最大值, 强制在线。

解题报告

分块+可持久化Trie搞。
自己zz现实写错数组名然后又忘记在查询块间最大值时把左右端点去掉不停wa…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int MAXN = 24200;
namespace PTrie {
    const int MAXD = MAXN*33;
    struct Node {
        int ch[2], tim;
    } d[MAXD];
    int roots[MAXN], rtot, dtot;
    void insert (int num) {
        int r = roots[rtot];
        int u = roots[++rtot] = ++dtot;
        d[u].tim = rtot;
        for(int i = 30; i>=0; i--) {
            bool f = num&(1<<i);
            d[u].ch[!f] = d[r].ch[!f];
            d[u].ch[f] = ++dtot;
            d[u = d[u].ch[f]].tim = rtot;
            r = d[r].ch[f];
        }
    }
    inline int query (int lb, int rb, int num) {
        int ret = 0;
        int u = roots[rb];
        for(int i = 30; i>=0; i--) {
            bool f = !(num&(1<<i));
            if(d[d[u].ch[f]].tim < lb) {
                u = d[u].ch[!f];
                if(!f) ret |= 1<<i;
            } else {
                u = d[u].ch[f];
                if(f) ret |= 1<<i;
            }
        }
        return ret^num;
    }
}
int N, M, A[MAXN];
int qsize = 128, qtot;
vector<int> qelem[110];
int qcross[110][110], qintv[110][110];
inline void initialize () {
    for(int i = 1; i<=N; ) {
        int j; ++ qtot;
        for(j = 0; j<qsize&&i+j<=N; j++)
            qelem[qtot].push_back(A[i+j]), PTrie::insert(A[i+j]);
        i += j;
    }
    for(int i = 1; i<=qtot; i++)
        for(int j = i; j<=qtot; j++) {
            int lb = (j-1)*qsize+1, rb = min(j*qsize, N);
            for(int k = 0; k<(int)qelem[i].size(); k++)
                qcross[i][j] = max(qcross[i][j], PTrie::query(lb, rb, qelem[i][k]));
        }
    for(int i = 1; i<=qtot; i++)
        for(int j = i; j<=qtot; j++)
            qcross[i][j] = max(qcross[i][j], qcross[i][j-1]);
    for(int j = 1; j<=qtot; j++)
        for(int i = j; i; i--)
            qintv[i][j] = max(qintv[i+1][j], qcross[i][j]);
}
inline int query (int l, int r) {
    int ret = 0;
    int ql = (l-1)/qsize+1, qr = (r-1)/qsize+1;
    if(ql == qr) {
        for(int i = l; i<=r; i++)
            ret = max(ret, PTrie::query(l, r, A[i]));
        return ret;
    }
    ret = max(ret, qintv[ql+1][qr-1]);
    int edgl = ql*qsize, edgr = (qr-1)*qsize+1;
    for(int i = l; i<=edgl; i++) ret = max(ret, PTrie::query(l, r, A[i]));
    for(int i = edgr; i<=r; i++) ret = max(ret, PTrie::query(l, r, A[i]));
    return ret;
}
int main () {
    scanf("%d%d", &N, &M);
    N++;
    for(int i = 2; i<=N; i++) scanf("%d", &A[i]);
    for(int i = 2; i<=N; i++) A[i] ^= A[i-1];
    initialize();
    int lastans = 0;
    while(M --) {
        int a, b;
        scanf("%d%d", &a, &b);
        a = ((LL)a+lastans)%(N-1)+1, b = ((LL)b+lastans)%(N-1)+1;
        if(a > b) swap(a, b);
        if(a == b) printf("%d\n", lastans = A[b+1]^A[b]);
        else printf("%d\n", lastans = query(a, b+1));
    }

}

BZOJ 2653

题目大意: 给你一个数列A, 每次给定(a, b, c, d)询问所有区间[l, r]满足a≤l≤b且c≤r≤d的区间中位数最大值。

解题报告

二分答案mid, 让小于mid的数权值为-1, 大于等于mid的数权值为1, 在主席树上查询[a, b)最大后缀+[b, c]的和+(c, d]最大前缀就是最优区间, 继续二分即可。
题目很好, 只是我个zz写反suffix和prefix导致wa到生无可恋…感谢SunIsMe。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 20020;
int N, len;
namespace PST {
    const int MAXD = MAXN*30;
    int lc[MAXD], rc[MAXD], dtot;
    int mxp[MAXD], mxs[MAXD], sum[MAXD];
    int roots[MAXN], rtot = 1;
    inline void updata (int u) {
        mxs[u] = max(mxs[rc[u]], sum[rc[u]]+mxs[lc[u]]);
        mxp[u] = max(mxp[lc[u]], sum[lc[u]]+mxp[rc[u]]);
    }
    int insp, insv;
    void insert (int & u, int lb, int rb, int r) {
        if(lb > insp || rb < insp) return ;
        if(!u) sum[u = ++dtot] = sum[r];
        sum[u] += insv;
        if(lb == rb) {mxp[u] = max(sum[u], 0), mxs[u] = max(sum[u], 0); return ;}
        int mid = (lb+rb)>>1;
        insert(lc[u], lb, mid, lc[r]);
        insert(rc[u], mid+1, rb, rc[r]);
    }
    inline void handleInsert (int p, int val) {
        insp = p, insv = val;
        insert(roots[rtot], 1, N, roots[rtot-1]);
    }
    inline void solidfy (int & u, int lb, int rb, int r) {
        if(!u) {u = r; return ;}
        if(lb == rb) return ;
        int mid = (lb+rb)>>1;
        solidfy(lc[u], lb, mid, lc[r]);
        solidfy(rc[u], mid+1, rb, rc[r]);
        updata(u);
    }
    inline void solidfyFloor () {
        solidfy(roots[rtot], 1, N, roots[rtot-1]);
        rtot ++;
    }
    int tar;
    int ql, qr;
    pair<int, int> querySuffix (int u, int lb, int rb) {
        if(ql <= lb && rb <= qr) return make_pair(sum[u], mxs[u]);
        if(!u || lb > qr || rb < ql) return make_pair(0, 0);
        int mid = (lb+rb)>>1;
        pair<int, int> lef = querySuffix(lc[u], lb, mid);
        pair<int, int> rig = querySuffix(rc[u], mid+1, rb);
        return make_pair(lef.first+rig.first, max(lef.second+rig.first, rig.second));
    }
    inline int hQueryPrefix (int a, int b) {
        ql = a, qr = b;
        return queryPrefix(tar, 1, N).second;
    }
    pair<int, int> queryPrefix (int u, int lb, int rb) {
        if(ql <= lb && rb <= qr) return make_pair(sum[u], mxp[u]);
        if(!u || lb > qr || rb < ql) return make_pair(0, 0);
        int mid = (lb+rb)>>1;
        pair<int, int> lef = queryPrefix(lc[u], lb, mid);
        pair<int, int> rig = queryPrefix(rc[u], mid+1, rb);
        return make_pair(lef.first+rig.first, max(rig.second+lef.first, lef.second));
    }
    inline int hQuerySuffix (int a, int b) {
        ql = a, qr = b;
        return querySuffix(tar, 1, N).second;
    }
    int querySum (int u, int lb, int rb) {
        if(!u || lb > qr || rb < ql) return 0;
        if(ql <= lb && rb <= qr) return sum[u];
        int mid = (lb+rb)>>1;
        return querySum(lc[u], lb, mid)+querySum(rc[u], mid+1, rb);
    }
    int hQuerySum (int a, int b) {ql = a, qr = b; return querySum(tar, 1, N);}
    inline void setTarget (int x) {tar = roots[x];}
}
int A[MAXN], linr[MAXN];
int img[MAXN], rev[MAXN];
vector<int> rk[MAXN];
int handleQuery (int a, int b, int c, int d) {
    //printf("qry:[(%d, %d), (%d, %d)]\n", a, b, c, d);
    int lb = 1, rb = len, ans = 0;
    while(lb <= rb) {
        int mid = (lb+rb)>>1;
        //printf("cur:[%d, %d], mid:%d(var:%d)\n", lb, rb, mid, rev[mid]);
        PST::setTarget(mid-1);
        int sum = PST::hQuerySum(b, c);
        int prefix = PST::hQuerySuffix(a, b-1);
        int suffix = PST::hQueryPrefix(c+1, d);
        //printf("pre:%d, sum:%d, suf:%d\n", prefix, sum, suffix); // -1:小的
        if(prefix+sum+suffix < 0) rb = mid-1;
        else lb = mid+1, ans = mid;
    }
    return rev[ans];
}
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%d", &A[i]), linr[i] = A[i];
    sort(linr+1, linr+N+1); len = (unique(linr+1, linr+N+1)-linr)-1;
    for(int i = 1; i<=N; i++)
        rev[img[i] = lower_bound(linr+1, linr+len+1, A[i])-linr] = A[i];
    for(int i = 1; i<=N; i++) rk[img[i]].push_back(i);
    for(int i = 1; i<=N; i++) PST::handleInsert(i, 1);
    for(int i = 1; i<=len; i++) {
        for(int j = 0; j<(int)rk[i].size(); j++)
            PST::handleInsert(rk[i][j], -2);
        PST::solidfyFloor();
    }

    int Q, lastans = 0;
    scanf("%d", &Q);
    for(int i = 1; i<=Q; i++) {
        int q[5];
        scanf("%d%d%d%d", &q[0], &q[1], &q[2], &q[3]);
        for(int i = 0; i<4; i++) q[i] = (q[i]+lastans)%N+1;
        sort(q, q+4);
        printf("%d\n", lastans = handleQuery(q[0], q[1], q[2], q[3]));
    }
}

BZOJ 3123

题目大意: 给你一个森林, 点带权, 每次加一条边或者询问两个节点间的路径上点权第k大的节点, 保证随时随刻这都是一个森林。

解题报告

对于单颗树, 用类似主席树的东西可以在dfn序上维护权值线段树, 然后求出lca后可以在权值线段树上二分。
对于link操作, 启发式暴力合并即可。lca询问使用st表, 每次合并时暴力更新, PST记得回收内存(貌似不回收也可以?)。
思路很不错, 以前都没看过这种题。自己不知道最近怎么了诸事不顺…写了30min调了1h+…最后发现是并查集忘记合并了…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 80080;
int len;
namespace PST {
    const int MAXD = MAXN*300;
    int lc[MAXD], rc[MAXD], sum[MAXD], dtot;
    int memstk[MAXD], stktop;
    bool isusing[MAXD];
    inline int newNode () {
        int u;
        if(stktop) u = memstk[stktop--];
        else u = ++dtot;
        isusing[u] = true;
        return u;
    }
    inline void erase (int u) {
        isusing[u] = false;
        sum[u] = lc[u] = rc[u] = 0;
        memstk[++stktop] = u;
    }
    void release (int u) {
        if(!isusing[u]) return ;
        erase(u);
        release(lc[u]), release(rc[u]);
    }
    int insp, insv;
    void insert (int & u, int lb, int rb, int r) {
        if(lb > insp || rb < insp) {u = r; return ;}
        sum[u = ++dtot] = sum[r]+insv;
        if(lb == rb) return ;
        int mid = (lb+rb)>>1;
        insert(lc[u], lb, mid, lc[r]);
        insert(rc[u], mid+1, rb, rc[r]);
    }
    int queryKth (int a, int b, int lca1, int lca2, int k) { // where 'a', 'b', 'lcaid' are segment tree nodes.
        int lb = 1, rb = len;
        while(lb != rb) {
            int mid = (lb+rb)>>1;
            int cur = sum[lc[b]]+sum[lc[a]]-sum[lc[lca1]]-sum[lc[lca2]];
            if(cur >= k) a = lc[a], b = lc[b], lca1 = lc[lca1], lca2 = lc[lca2], rb = mid;
            else a = rc[a], b = rc[b], lca1 = rc[lca1], lca2 = rc[lca2], k -= cur, lb = mid+1;
        }
        return lb;
    }
}
struct Node {
    int v, nxt;
} d[MAXN*3];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
    etot ++;
    d[etot].v = b;
    d[etot].nxt = head[a];
    head[a] = etot;
}
int A[MAXN], rev[MAXN], linr[MAXN];
int pos[MAXN], plast[MAXN];
int dep[MAXN], sz[MAXN], fa[MAXN][18];
int pfa[MAXN];
int root(int a) {return pfa[a] ? pfa[a] = root(pfa[a]) : a;}
int dfs (int u, int f) {
    dep[u] = dep[f]+1;
    fa[u][0] = f;
    for(int lvl = 1; lvl<18; lvl++)
        fa[u][lvl] = fa[fa[u][lvl-1]][lvl-1];
    sz[u] = 1;
    PST::release(pos[u]), pos[u] = 0; // clear memory
    PST::insp = A[u], PST::insv = 1;
    PST::insert(pos[u], 1, len, pos[f]);
    for(int e = head[u]; e; e = d[e].nxt) {
        if(d[e].v == f) continue ;
        sz[u] += dfs(d[e].v, u);
    }
    return sz[u];
}
int getLCA (int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 17; i>=0; i--)
        if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    if(a == b) return a;
    for(int i = 17; i>=0; i--)
        if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    return fa[a][0];
}
char buf[6];
int main () {
    scanf("%*d");
    int N, M, T;
    scanf("%d%d%d", &N, &M, &T);
    for(int i = 1; i<=N; i++)
        scanf("%d", &A[i]);
    memcpy(linr, A, sizeof A);
    sort(linr+1, linr+N+1);
    len = (unique(linr+1, linr+N+1)-linr)-1;
    for(int i = 1; i<=N; i++) {
        int t = lower_bound(linr+1, linr+len+1, A[i])-linr;
        rev[t] = A[i], A[i] = t;
    }
    for(int i = 1; i<=M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        addEdge(a, b), addEdge(b, a);
        pfa[root(b)] = root(a);
    }
    for(int i = 1; i<=N; i++)
        if(root(i) == i) dfs(i, 0);
    int lastans = 0;
    for(int i = 1; i<=T; i++) {
        scanf("%s", buf);
        int a, b, c;
        if(buf[0] == 'Q') {
            scanf("%d%d%d", &a, &b, &c);
            a ^= lastans, b ^= lastans, c ^= lastans;
            int lca = getLCA(a, b);
            lastans = rev[PST::queryKth(pos[a], pos[b], pos[fa[lca][0]], pos[lca], c)];
            printf("%d\n", lastans);
        } else {
            scanf("%d%d", &a, &b);
            a ^= lastans, b ^= lastans;
            int ra = root(a), rb = root(b);
            if(sz[ra] > sz[rb]) swap(a, b), swap(ra, rb);
            addEdge(a, b), addEdge(b, a);
            sz[rb] += sz[ra], pfa[ra] = rb;
            dfs(a, b);
        }
    }
}

BZOJ 3207

题目大意:给你一个串, 每次询问一个长度为一常数K的串是否在原串区间[l, r]中作为子串出现过。

解题报告

哎Hineven傻不傻的没有看到查询长度为一个常数K…
怎么做呢…先跑后缀数组然后哈希+二分lcp处理处区间后进在二位数据结构上查询…
什么? 查询的长度是常数?
开始苟且…
《论哈希与STLの胜利 II》

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const ULL SEED = 100019;
const int MAXN = 1000010;
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '0');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
ULL hashv[MAXN];
int A[MAXN];
map<ULL, set<int> > mp;
int main () {
    int N = getInt(), M = getInt(), K = getInt();
    for(int i = 1; i<=N; i++)
        A[i] = getInt(), hashv[i] = hashv[i-1]*SEED+A[i];
    ULL prK = 1;
    for(int i = 1; i<=K; i++) prK = prK*SEED;
    for(int i = 1; i<=N-K+1; i++) mp[hashv[i+K-1]-hashv[i-1]*prK].insert(i);
    for(int i = 1; i<=M; i++) {
        int l = getInt(), r = getInt();
        ULL code = 0;
        for(int j = 1; j<=K; j++)
            code = code*SEED+getInt();
        set<int> & st = mp[code];
        set<int>::iterator it = st.lower_bound(l);
        if(it == st.end() || *it > r-K+1) puts("Yes");
        else puts("No");
    }
}

BZOJ 3261

题目大意: 给一个序列A, 要求支持两种操作:
1.在末尾插入元素。
2.给定l, r和x, 对于i满足i属于[l, r], 问所有A[i]^A[i+1]^…^A[末尾]^x的最大值。

解题报告

异或和贪心题层出不尽…然并卵。
设前缀异或和为sig[i], 那么后缀异或和就是sum(总异或和)^sig[i-1], 维护后缀转化为维护前缀。
然后把sig[i-1]拿去建立可持久化Trie, 查询时将sig[末尾]^x扔给Trie在区间上跑贪心即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int MAXN = 600060;
namespace PTrie {
    const int MAXD = MAXN*30;
    struct Node {
        int ch[2];
        int tim;
    } d[MAXD];
    int dtot;
    int roots[MAXN], rtot;
    inline void insert (int num) {
        int u = roots[++rtot] = ++dtot;
        d[u].tim = rtot;
        int r = roots[rtot-1];
        for(int i = 25; i>=0; i--) {
            bool f = num&(1<<i);
            d[u].ch[!f] = d[r].ch[!f];
            d[u = (d[u].ch[f] = ++dtot)].tim = rtot;
            r = d[r].ch[f];
        }
    }
    inline int query (int lb, int rb, int num) {
        int u = roots[rb], ret = 0;
        for(int i = 25; i>=0; i--) {
            bool f = !(num&(1<<i));
            if(d[d[u].ch[f]].tim >= lb) {
                u = d[u].ch[f];
                if(f) ret = ret|(1<<i);
            } else {
                u = d[u].ch[!f];
                if(!f) ret = ret|(1<<i);
            }
        }
        return ret^num;
    }
}
inline int getInt () {
    int ret; char ch;
    while((ch = getchar()) < '0' || ch > '9') ;
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        ret = ret*10+(ch-'0');
    return ret;
}
int sig[MAXN], cur;
int main () {
    int N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++) {
        sig[i] = getInt()^sig[i-1];
        PTrie::insert(sig[i-1]);
    }
    char buf[5];
    for(int i = 1; i<=M; i++) {
        scanf("%s", buf);
        if(buf[0] == 'A') {
            PTrie::insert(sig[N]);
            sig[N+1] = getInt()^sig[N], N++;
        } else {
            int a = getInt(), b = getInt();
            printf("%d\n", PTrie::query(a, b, getInt()^sig[N]));
        }
    }
}

BZOJ 2588

题目大意: 给你一棵树, 树点带权, 每次询问一条路径上的节点权值第k小。

解题报告

模板题, 类主席树上。
打错变量len+1<-N+1, wa*3。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 200020;
int len;
namespace PST {
    const int MAXD = MAXN*30;
    int lc[MAXD], rc[MAXD], sum[MAXD], dtot;
    int insp;
    void insert (int&u, int lb, int rb, int r) {
        if(lb > insp || rb < insp) {u = r; return ;}
        sum[u = ++dtot] = sum[r]+1;
        if(lb == rb) return ;
        int mid = (lb+rb)>>1;
        insert(lc[u], lb, mid, lc[r]);
        insert(rc[u], mid+1, rb, rc[r]);
    }
    inline int queryKth (int a, int b, int l1, int l2, int k) {
        int lb = 1, rb = len;
        while(lb < rb) {
            int mid = (lb+rb)>>1;
            int cur = sum[lc[a]]+sum[lc[b]]-sum[lc[l1]]-sum[lc[l2]];
            if(cur >= k) a = lc[a], b = lc[b], l1 = lc[l1], l2 = lc[l2], rb = mid;
            else a = rc[a], b = rc[b], l1 = rc[l1], l2 = rc[l2], k -= cur, lb = mid+1;
        }
        return lb;
    }
}
int N, M;
struct Node {
    int v, nxt;
} d[MAXN*2];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
    etot ++;
    d[etot].v = b;
    d[etot].nxt = head[a];
    head[a] = etot;
}
int A[MAXN], linr[MAXN];
int uid[MAXN], sz[MAXN];
int top[MAXN], dep[MAXN], fa[MAXN];
int dfs (int u, int f) {
    sz[u] = 1, fa[u] = f, dep[u] = dep[f]+1;
    PST::insp = A[u], PST::insert(uid[u], 1, len, uid[f]);
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f) sz[u] += dfs(d[e].v, u);
    return sz[u];
}
void chainDivide (int u, int f) {
    if(!top[u]) top[u] = u;
    int mxp = 0;
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f && sz[d[e].v] >= sz[mxp]) mxp = d[e].v;
    if(!mxp) return ;
    top[mxp] = top[u];
    chainDivide(mxp, u);
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f && d[e].v != mxp)
            chainDivide(d[e].v, u);
}
inline int getLCA (int a, int b) {
    while(top[a] != top[b]) {
        if(dep[top[a]] > dep[top[b]]) a = fa[top[a]];
        else b = fa[top[b]];
    }
    return dep[a] > dep[b] ? b : a;
}
inline int getInt () {
    LL ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int main () {
    N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++)
        A[i] = getInt();
    memcpy(linr, A, sizeof A);
    sort(linr+1, linr+N+1);
    len = (unique(linr+1, linr+N+1)-linr)-1;
    for(int i = 1; i<=N; i++)
        A[i] = lower_bound(linr+1, linr+len+1, A[i])-linr;
    for(int i = 1; i<N; i++) {
        int a = getInt(), b = getInt();
        addEdge(a, b), addEdge(b, a);
    }
    int lastans = 0;
    dfs(1, 0), chainDivide(1, 0);
    for(int i = 1; i<=M; i++) {
        int a = getInt()^lastans, b = getInt();
        int lca = getLCA(a, b);
        printf("%d", lastans = linr[
        PST::queryKth(uid[a], uid[b], uid[lca], uid[fa[lca]], getInt())]);
        if(i != M) putchar('\n');
    }
}