杂题训练(一)

前言

一开始以为是一坨数据结构, 结果是一坨杂题。

BZOJ 3306

题目大意: 给一棵带点权树, 要求支持:
1.单点点权修改。
2.子树点权最大值。
3.换根。

解题报告

据说正解是dfn序加上一些乱搞…但是lct明显是可以做的。
在lct上用multiset打标记表示子树最大值, 复杂度多个log但是好写啊。
自己zz..prepare()里面写反updata和insert, 然后没能把自己的子树最大值更新上去…RE不断*1h+

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <set>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
namespace LCT {
    const int MAXD = MAXN;
    struct Node {
        int ch[2], fa;
        bool tfa, rev;
        int val, mx;
        multiset<int> vir;
    } d[MAXD];
    inline void initialize () {
        d[0].mx = INT_MIN;
        d[0].vir.insert(INT_MIN);
    }
    inline void updata (int u) {
        d[u].mx = max(
        max(d[u].val, *d[u].vir.rbegin()),
        max(d[d[u].ch[0]].mx, d[d[u].ch[1]].mx));
    }
    void makeNode (int u, int f, int v) {
        d[u].fa = f, d[u].mx = d[u].val = v;
        d[u].vir.insert(INT_MIN);
    }
    inline void prepare (int u) {
        updata(u);
        d[d[u].fa].vir.insert(d[u].mx);
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        swap(d[x].tfa, d[y].tfa);
        if(d[x].tfa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    inline void filp (int u) {
        d[u].rev ^= 1, swap(d[u].ch[0], d[u].ch[1]);
    }
    inline void pushdown (int u) {
        if(d[u].rev) {
            filp(d[u].ch[0]), filp(d[u].ch[1]);
            d[u].rev = false;
        }
    }
    void downlazy (int u) {
        if(d[u].fa && d[u].tfa) downlazy(d[u].fa);
        pushdown(u);
    }
    inline void splay (int x) {
        downlazy(x);
        while(d[x].tfa) {
            int y = d[x].fa, z = d[y].fa;
            if(d[y].tfa) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
    }
    inline void access (int u) {
        int t = u, r = 0, tmp;
        while(u) {
            splay(u);
            if(d[u].ch[1]) d[u].vir.insert(d[d[u].ch[1]].mx);
            if(r) d[u].vir.erase(d[u].vir.find(d[r].mx));
            d[d[u].ch[1]].tfa = false;
            d[d[u].ch[1] = r].tfa = true;
            updata(u);
            r = u;
            u = d[u].fa;
        }
        splay(t);
    }
    inline void makeroot (int u) {
        access(u), filp(u);
    }
    inline int maxValue (int u) {
        access(u);
        return max(*d[u].vir.rbegin(), d[u].val);
    }
    inline void modify (int u, int v) {
        access(u), d[u].val = v, updata(u);
    }
}
inline int getInt () {
    int 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;
}
char buf[20];
int main () {
    int N = getInt(), Q = getInt();
    LCT::initialize();
    for(int i = 1; i<=N; i++) {
        int f = getInt(), v = getInt();
        LCT::makeNode(i, f, -v);
    }
    for(int i = N; i>=2; i--)
        LCT::prepare(i);
    LCT::updata(1);
    while(Q --) {
        scanf("%s", buf);
        int x = getInt();
        if(buf[0] == 'V') LCT::modify(x, -getInt());
        else if(buf[0] == 'E') LCT::makeroot(x);
        else printf("%d\n", -LCT::maxValue(x));
    }
}

BZOJ 3991

题目大意: 给你一颗树, 每次把一个点的选取状态取反, 对每次操作输出操作后所有被选取点组成的子树边权和乘二。

解题报告

什么lct!虚树!
每次把dfn前驱和后继拉出来做lca算delta即可。
注意这题dfn成环, 自己脑残了总是写不过…

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <set>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
inline int getInt () {
    int 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;
}
struct Node {
    int v, w, nxt;
} d[MAXN*2];
int head[MAXN], etot;
inline void addEdge (int a, int b, int c) {
    etot ++;
    d[etot].v = b;
    d[etot].w = c;
    d[etot].nxt = head[a];
    head[a] = etot;
}
int dfn[MAXN], rev[MAXN], lst[MAXN], dfntot;
int sz[MAXN], top[MAXN], fa[MAXN], depu[MAXN];
LL dep[MAXN];
int dfsSize (int u, int f) {
    rev[dfn[u] = ++dfntot] = u;
    sz[u] = 1;
    depu[u] = depu[f]+1;
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f) {
            dep[d[e].v] = dep[u]+d[e].w;
            sz[u] += dfsSize(d[e].v, u);
        }
    lst[u] = dfntot;
    return sz[u];
}
void dfs (int u, int f) {
    fa[u] = 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], dfs(mxp, u);
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f && d[e].v != mxp) dfs(d[e].v, u);
}
inline int getLCA (int a, int b) {
    //printf("calt:%d, %d\n", a, b);
    while(top[a] != top[b]) {
        if(depu[top[a]] < depu[top[b]]) b = fa[top[b]];
        else a = fa[top[a]];
    }
    return depu[a] < depu[b] ? a : b;
}
inline LL getDist (int a, int b) {
    int lca = getLCA(a, b);
    return dep[a]+dep[b]-dep[lca]*2LL;
}
LL ans = 0;
set<int> st;
int main () {
    int N = getInt(), M = getInt();
    for(int i = 1; i<N; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addEdge(a, b, c), addEdge(b, a, c);
    }
    dfsSize(1, 0);
    dfs(1, 0);
    while(M --) {
        int u = getInt();
        set<int>::iterator it1, it2;
        int x1 = 0, x2 = 0;
        it1 = st.lower_bound(dfn[u]);
        if(st.size() == 0) {
            st.insert(dfn[u]);
            puts("0");
            continue ;
        }
        if(it1 == st.end() || *it1 != dfn[u]) { // not exist
            if(it1 != st.end()) x2 = rev[*it1];
            else x2 = rev[*st.begin()];
            if(it1 != st.begin()) {
                --it1;
                x1 = rev[*it1];
            } else it2 = st.end(), x1 = rev[*(--it2)];
            st.insert(dfn[u]);
            if(x1 != 0 && x2 != 0) ans += getDist(x1, u)+getDist(u, x2)-getDist(x1, x2);
            else if(x1+x2 != 0 && (x1 == 0 || x2 == 0)) ans += 2*getDist(x1+x2, u);
        } else {
            it2 = it1, it2++;
            st.erase(it1);
            if(it2 != st.end()) x2 = rev[*it2];
            else x2 = rev[*st.begin()];
            if(it2 != st.begin()) {
                --it2;
                x1 = rev[*it2];
            } else it2 = st.end(), x1 = rev[*(--it2)];
            if(x1 != 0 && x2 != 0) ans -= getDist(x1, u)+getDist(u, x2)-getDist(x1, x2);
            else if(x1+x2 != 0 && (x1 == 0 || x2 == 0)) ans -= 2*getDist(x1+x2, u);
        }
        printf("%lld\n", ans);
    }
}

BZOJ 2947

题目大意: 算了这题太水就不写了…
←懒人…

BZOJ 3544

题目大意: 给你一个数列, 询问数列区间和在模M意义下的最大值。

解题报告

又不是LCT
很水的…直接在set里挨个插入前缀和, 然后查询时差分, 按照贪心思想upper_bound一个相减即可。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <iostream>
#include <set>
using namespace std;
typedef long long LL;
inline LL 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;
}
set<LL> st;
int main () {
    int N = getInt(); LL M = getInt();
    LL sum = 0, ans = 0;
    st.insert(0);
    for(int i = 1; i<=N; i++) {
        sum = (sum+getInt()%M+M)%M;
        set<LL>::iterator it = st.upper_bound(sum);
        if(it == st.end()) it = st.begin();
        ans = max(ans, (sum-*it+M)%M);
        //printf("cur:%I64d, find:%I64d\n", sum, *it);
        st.insert(sum);
    }
    cout << ans << '\n';
}

BZOJ 2300

题目大意: 在线动态上凸包。

解题报告

就是个版…
自己计算几何太弱了..判凸包写错…叉乘写错…调了30min+

代码

#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <set>
using namespace std;
const int MAXN = 100010;
const int MAXQ = 200020;
struct Vector {
    int x, y;
    Vector () {}
    Vector (double a, double b):x(a), y(b) {}
    inline Vector operator + (const Vector & b) const
    {return Vector(x+b.x, y+b.y);}
    inline Vector operator - (const Vector & b) const
    {return Vector(x-b.x, y-b.y);}
};
inline int cross (const Vector & a, const Vector & b) {
    return a.x*b.y-a.y*b.x;
}
inline double getDist (const Vector & a, const Vector & b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline int getInt () {
    int 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 ret;
}
inline bool operator < (const Vector & a, const Vector & b) {
    if(a.x == b.x) return a.y<b.y;
    return a.x<b.x;
}
namespace DynamicHull {
    multiset<Vector> st;
    double cur_perimeter;
    void initialize (Vector a, Vector b, Vector c) { // 逆时针
        st.clear();
        st.insert(a), st.insert(b), st.insert(c);
        cur_perimeter = getDist(a, b)+getDist(b, c);
    }
    void insert (Vector vec) {
        multiset<Vector>::iterator it1 = st.lower_bound(vec), it2 = it1, tmp;
        it1--;
        if(cross(*it2-*it1, vec-*it1) <= 0) return ;
        cur_perimeter -= getDist(*it1, *it2);
        while(it1 != st.begin()) {
            tmp = it1, tmp--;
            if(cross(vec-*tmp, vec-*it1) >= 0) {
                cur_perimeter -= getDist(*tmp, *it1), st.erase(it1);
                it1 = tmp;
            } else break;
        }
        while(it2 != st.end()) {
            tmp = it2, tmp++;
            if(tmp == st.end()) break;
            if(cross(*tmp-vec, *it2-vec) <= 0) {//(3, -2)(2, 0)
                //printf("(%.2lf, %.2lf), (%.2lf, %.2lf)\n", it2->x, it2->y, tmp->x, tmp->y);
                cur_perimeter -= getDist(*tmp, *it2), st.erase(it2);
                it2 = tmp;
            } else break;
        }
        cur_perimeter += getDist(*it1, vec)+getDist(vec, *it2);
        st.insert(vec);
    }
    inline double perimeter () {return cur_perimeter;}
}
double ans[MAXQ];
Vector pos[MAXN];
int comd[MAXQ], arg[MAXQ];
bool vis[MAXN];
int main () {
    int N = getInt(), X = getInt(), Y = getInt();
    int M = getInt();
    for(int i = 1; i<=M; i++) pos[i].x = getInt(), pos[i].y = getInt();
    int Q = getInt();
    for(int i = 1; i<=Q; i++) {
        comd[i] = getInt();
        if(comd[i] == 1)
            vis[arg[i] = getInt()] = true;
    }
    DynamicHull::initialize(Vector(0, 0), Vector(X, Y), Vector(N, 0));
    for(int i = 1; i<=M; i++)
        if(!vis[i]) DynamicHull::insert(pos[i]);
    for(int i = Q; i; i--) {
        if(comd[i] == 1 && vis[arg[i]])
            vis[arg[i]] = false, DynamicHull::insert(pos[arg[i]]);
        else ans[i] = DynamicHull::perimeter();
    }
    for(int i = 1; i<=Q; i++)
        if(comd[i] == 2) printf("%.2lf\n", ans[i]);
}

BZOJ 4260

题目大意: 盗图!

解题报告

最大区间异或和模板, 注意Trie清0时一定要清根节点…浪费时间+wa*3

代码

#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <set>
using namespace std;
const int MAXN = 400040;
namespace Trie {
    const int MAXD =  400040*31;
    struct Node {
        int ch[2];
    } d[MAXD];
    int dtot;
    void clear() {
        dtot = 0;
        memset(d, 0, sizeof d[0]);
    }
    inline int newNode () {memset(d+(++dtot), 0, sizeof d[0]); return dtot;}
    inline void insert (int num) {
        int u = 0, bit = 29;
        while(bit>=0) {
            bool flg = (bool)(num&(1<<bit));
            if(!d[u].ch[flg])
                d[u].ch[flg] = newNode();
            u = d[u].ch[flg];
            -- bit;
        }
    }
    inline int query (int num) {
        int u = 0, bit = 29, ret = 0;
        while(bit>=0) {
            bool flg = !(bool)(num&(1<<bit));
            if(!d[u].ch[flg]) u = d[u].ch[flg = !flg];
            else u = d[u].ch[flg];
            ret |= ((int)flg)<<bit;
            -- bit;
        }
        return ret;
    }
}
inline int getInt () {
    int 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 A[MAXN], mxv[MAXN];
int main () {
    int N = getInt();
    for(int i = 1; i<=N; i++) A[i] = getInt();
    int cur = 0;
    Trie::insert(0);
    for(int i = 1; i<=N; i++) {
        cur ^= A[i];
        Trie::insert(cur);
        mxv[i] = max(mxv[i-1], Trie::query(cur)^cur);
    }
    Trie::clear(), cur = 0;
    Trie::insert(0);
    int ans = 0;
    for(int i = N; i>=2; i--){
        cur ^= A[i];
        Trie::insert(cur);
        ans = max(ans, (Trie::query(cur)^cur)+mxv[i-1]);
    }
    printf("%d\n", ans);
}

BZOJ 1492

CDQ写炸了…但是暂时不想补…留个坑…

BZOJ 4026

题目大意: 给你一个数组, 每次询问一个下标在区间[l, r]内元素乘积的欧拉函数, 对1e6+777取模。

解题报告

一开始想错, 然后各种zz错, 和这道题玩了好久…题目还是比较不错的
把欧拉函数展开之后可以转化为二维矩阵乘积问题, 由于没有修改用主席树维护。
我的主席树为什么比别人慢那么多…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long LL;
const int MOD = 1000777;
const int MAXN = 50050;
vector<int> fac[MOD];
bool isnprime[MOD]; int prec[MOD/3], ptot;
int inv[MOD];
void preProcess (int lim) {
    for(int i = 2; i<lim; i++) {
        if(!isnprime[i]) {prec[++ptot] = i; fac[i].push_back(i);}
        for(int j = 1; j<=ptot&&prec[j]*i < lim; j++) {
            fac[prec[j]*i] = fac[i];
            fac[prec[j]*i].push_back(prec[j]);
            isnprime[prec[j]*i] = true;
            if(i%prec[j] == 0) break;
        }
    }
    inv[1] = 1;
    for(int i = 2; i<MOD; i++)
        inv[i] = (MOD-(LL)(MOD/i)*inv[MOD%i]%MOD)%MOD;
    fac[1].push_back(1);
}
inline int inverse (int a) {return inv[a%MOD];}
int N, Q;
namespace PST {
    const int MAXD = 6800000;
    int val[MAXD], lc[MAXD], rc[MAXD], dtot;
    int roots[MAXN], tot = 1;
    void initialize () {val[0] = 1;}
    void solidfy(int & u, int r) {
        if(!u) u = r;
        else {
            solidfy(lc[u], lc[r]);
            solidfy(rc[u], rc[r]);
        }
    }
    inline void solidfyFloor () {solidfy(roots[tot], roots[tot-1]); ++tot;}
    int pos, ins;
    void insertF (int & u, int lb, int rb, int r) {
        if(lb > pos || rb < pos) return ;
        if(!u) u = ++dtot, val[u] = val[r];
        val[u] = (LL)val[u]*ins%MOD;
        if(lb == rb) return ;
        int mid = (lb+rb)>>1;
        insertF(lc[u], lb, mid, lc[r]);
        insertF(rc[u], mid+1, rb, rc[r]);
    }
    void insert (int p, int v) {
        pos = p, ins = v;
        //printf("ins:p:%d, v:%d\n", p, v);
        insertF(roots[tot], 1, N, roots[tot-1]);
    }
    int ql, qr;
    int queryF (int & u, int lb, int rb) {
        if(!u || lb > qr || rb < ql) return 1;
        if(lb >= ql && rb <= qr) return val[u];
        int mid = (lb+rb)>>1;
        return (LL)queryF(lc[u], lb, mid)*queryF(rc[u], mid+1, rb)%MOD;
    }
    int query (int L, int R) {
        ql = L, qr = R;
        int x = queryF(roots[R], 1, N);
        return (LL)x*inverse(queryF(roots[L-1], 1, N))%MOD;
    }
}
inline int getInt () {
    int 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 A[MAXN], lst[MOD];
int main () {
    N = getInt(), Q = getInt();
    int mxv = 0;
    PST :: initialize();
    for(int i = 1; i<=N; i++) A[i] = getInt(), mxv = max(mxv, A[i]);
    preProcess(mxv+1);
    for(int i = 1; i<=N; i++) {
        //printf("cur:%d\n", A[i]);
        for(int j = 0; j<(int)fac[A[i]].size(); j++) {
            int x = fac[A[i]][j];
            if(lst[x]) PST::insert(lst[x], (LL)inverse(x-1)*x%MOD);
            if(x != 1) PST::insert(lst[x]=i, x-1);
        }
        PST::solidfyFloor();
    }
    int lastans = 0;
    for(int i = 1; i<=Q; i++) {
        int L = getInt()^lastans, R = getInt()^lastans;
        printf("%d\n", lastans=PST::query(L, R));
    }
}
/*
10 10
1 87 267 1 3287 268 29 165 87 11
2 8
*/

月考

月考了一波, 怀疑人生。
cqbz按照排名来分考试, 分数越高, 考试座位号越靠前, 考室号称之为’段位’。
好不容易上了王者, 停课掉到钻石, 化学64pts, 这次怕不止是要掉段, 还得坠楼了…

BZOJ 3658

题目大意: 二维平面上有N个最多K种颜色的点, 问选取一根平行于x轴的线段, 这根线段覆盖的点定义为线段上方(或下方)的所有点。
称一种覆盖是合法的当这种覆盖的所有点不包含全部K种颜色最多覆盖点数。

解题报告

好像做过?重新想, 扫描线+stl乱搞。
首先把每种颜色开一个set维护扫描线状态, 然后离散化一维用树状数组维护区间和扫描线做两遍即可。
具体看代码。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
#include <set>
#include <stack>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
inline int getInt () {
    int 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;
}
struct CoordPoint {
    int x, y, c;
} pos[MAXN], tmp[MAXN];
inline bool comp (const CoordPoint & a, const CoordPoint & b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
inline bool compY (const CoordPoint & a, const CoordPoint & b) {
    if(a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
int N, K;
int C[MAXN];
inline int lowbit (int a) {return a&-a;}
inline void add (int p) {
    while(p <= N) ++C[p], p += lowbit(p);
}
inline int query (int p) {
    int ret = 0;
    while(p) ret += C[p], p -= lowbit(p);
    return ret;
}
int ans;
set<int> st[MAXN]; stack<pair<int, int> > stk;
int itot;
void solve () {
    for(int i = 1; i<=K; i++) {
        st[i].clear();
        st[i].insert(0);
        st[i].insert(itot+1);
    }
    memset(C, 0, sizeof C);
    std :: sort(tmp+1, tmp+N+1, compY);
    for(int i = 1, p; i<=N; i=p) {
        p = i;
        while(tmp[i].y == tmp[p].y && p <= N) {
            add(tmp[p].x);
            if(st[tmp[p].c].find(tmp[p].x) != st[tmp[p].c].end())
                {++p; continue ;}
            stk.push(make_pair(tmp[p].c, tmp[p].x));
            st[tmp[p].c].insert(tmp[p].x), ++p;
        }
        while(!stk.empty()) {
            int x = stk.top().second, c = stk.top().first, lb, rb;
            stk.pop();
            set<int>::iterator it = st[c].find(x);
            --it; lb = *it;
            ++it, ++it, rb = *it;
            ans = max(ans, query(rb-1)-query(lb)-1);
        }
    }
    for(int c = 1; c<=K; c++) {
        set<int>::iterator it1 = st[c].begin(), it2 = it1;
        for(++it1; it1 != st[c].end(); it2=it1, it1++)
            ans = max(ans, query(*it1-1)-query(*it2));
    }
}
bool vis[MAXN];
int main () {
    int T = getInt();
    while(T --) {
        N = getInt(), K = getInt();
        memset(vis, 0, sizeof vis);
        for(int i = 1; i<=N; i++)
            pos[i].x = getInt(), pos[i].y = getInt(), vis[pos[i].c = getInt()] = true;
        bool flg = false;
        for(int i = 1; i<=K; i++)
            if(!vis[i]) {flg = true; break;}
        if(flg) {
            printf("%d\n", N);
            continue ;
        }
        std :: sort(pos+1, pos+N+1, comp);
        itot = 1;
        memcpy(tmp, pos, sizeof pos);
        tmp[1].x = itot;
        for(int i = 2; i<=N; i++)
            if(pos[i].x != pos[i-1].x) tmp[i].x = ++itot;
            else tmp[i].x = itot;
        ans = 0;
        solve();
        for(int i = 1; i<=N; i++) tmp[i].y = -tmp[i].y;
        solve();
        printf("%d\n", ans);
    }
}

BZOJ 3772

题目大意:给你一个树和M条路径, 问任意选择两条不相同路径恰好一条路径包含另一条的概率。

解题报告

如果路径是树上全部路径怎么做呢…
把路径用dfn转化为矩形然后上主席树维护, 注意包含和dfn序之间的转换不要太想当然了, 主席树手残在cpNode的时候顺便复制了lc和rc导致不断WA样例我太弱了…
卡内存, PST开50倍MLE了, 开45倍AC。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
inline int getInt () {
    int 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 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;
}
namespace PST {
    const int MAXD = MAXN*45;
    int sum[MAXD], lc[MAXD], rc[MAXD];
    int dtot, roots[MAXN], tot = 1;
    int insp;
    void cNodeTo (int a, int b) {sum[b] = sum[a];}
    void insert (int & u, int lb, int rb, int r) {
        if(lb > insp || rb < insp) return ;
        if(!u) u = ++dtot, cNodeTo(r, u);
        //printf("at:%d, insp:%d, bd:(%d, %d)\n", u, insp, lb, rb);
        sum[u]++;
        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 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 query(lc[u], lb, mid) + query(rc[u], mid+1, rb);
    }
    void solidfy (int & u, int r) {
        if(!u) u = r;
        else {
            solidfy(lc[u], lc[r]);
            solidfy(rc[u], rc[r]);
        }
    }
    inline int & root () {return roots[tot];}
    inline int & lroot () {return roots[tot-1];}
    inline void solidfyFloor () {
        solidfy(root(), lroot());
        ++ tot;
    }
    inline int queryRect (int a, int b, int c, int d) {
        if(b >= c) swap(a, c), swap(b, d);
        ql = c, qr = d;
        int re = query(roots[b], 1, N)-query(roots[a-1], 1, N);
        return re;
    }
}
int dfn[MAXN], lst[MAXN], rev[MAXN], dfntot;
int sz[MAXN], fa[MAXN], top[MAXN], dep[MAXN];
int dfs (int u, int f) {
    fa[u] = f, dep[u] = dep[f]+1;
    sz[u] = 1;
    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 dfsHv (int u, int f) {
    if(!top[u]) top[u] = u;
    rev[dfn[u] = ++dfntot] = 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) {lst[u] = dfntot; return ;}
    top[mxp] = top[u], dfsHv(mxp, u);
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f && d[e].v != mxp)
            dfsHv(d[e].v, u);
    lst[u] = dfntot;
}
int getLCA (int a, int b) {
    while(top[a] != top[b]) {
        if(dep[top[a]] < dep[top[b]]) b = fa[top[b]];
        else a = fa[top[a]];
    }
    return dep[a]<dep[b] ? a : b;
}
int jump (int a, int step) {
    while(step > dep[a]-dep[top[a]])
        step -= dep[a]-dep[top[a]]+1, a = fa[top[a]];
    return rev[dfn[a]-step];
}
struct Path {
    int a, b;
} prec[MAXN];
inline bool operator < (const Path & a, const Path & b) {
    return dfn[a.a] < dfn[b.a];
}
inline LL gcd (LL a, LL b) {return !b ? a : gcd(b, a%b);}
int main () {
    N = getInt(), M = getInt();
    for(int i = 1; i<N; i++) {
        int a = getInt(), b = getInt();
        addEdge(a, b), addEdge(b, a);
    }
    for(int i = 1; i<=M; i++)
        prec[i].a = getInt(), prec[i].b = getInt();
    dfs(1, 0);
    dfsHv(1, 0);
    for(int i = 1; i<=M; i++)
        if(dfn[prec[i].a] > dfn[prec[i].b])
            swap(prec[i].a, prec[i].b);
    std :: sort(prec+1, prec+M+1);
    int cur = 1;
    for(int i = 1; i<=N; i++) {
        while(cur <= M && dfn[prec[cur].a] == i) {
            PST::insp = dfn[prec[cur].b];
            PST::insert(PST::root(), 1, N, PST::lroot());
            cur++;
        }
        PST::solidfyFloor();
    }
    LL denominator = (LL)M*(M-1)/2, numerator = 0;
    for(int i = 1; i<=M; i++) {
        int a = prec[i].a, b = prec[i].b;
        int lca = getLCA(a, b);
        if(lca == a || lca == b) {
            if(lca == b) swap(a, b);
            int x = jump(b, dep[b]-dep[a]-1);
            numerator += PST::queryRect(1, dfn[x]-1, dfn[b], lst[b])-1; // 这个得函数内保证b<c
            numerator += PST::queryRect(lst[x]+1, N, dfn[b], lst[b]);
        } else numerator += PST::queryRect(dfn[a], lst[a], dfn[b], lst[b])-1;
    }
    LL g = gcd(numerator, denominator);
    numerator /= g, denominator /= g;
    printf("%lld/%lld\n", numerator, denominator);
}