某岛

… : "…アッカリ～ン . .. . " .. .

May 28, 2012

Codeforces Round #121

Brief description:

Problem A. Dynasty Puzzles
略。（.G[a][b] 表示以 a 开始 b 结尾的最长串的长度。。最后统计所有 G[a][a] ….

Problem B. Demonstration
读题压力巨大，那个啥。。大概的意思是有一个一行 n 的位置，每个位置有一个价值 ai …
然后对立的两个势力进行如下的博弈 .
..
A 势力（以下简称进攻方）的目的是得到一个尽可能靠左的位置，
每回合它可以选择任意一个位置占据。

B 势力（以下简称防御方）的目的是使得进攻方的结果尽可能糟糕，
。。每当进攻方选择了一个位置之后，防御方可以有以下两个决策。

1. 花费 ai 块钱。。让 A 势力滚回老家结婚。（该位置永远无法再次选择，并且 A 势力自动获得最靠右的那个格子）
2. 预算不足。。占据就占据吧。。

问一个 k 回合，防御方资金为 B 的游戏，进攻方所能得到的最好成绩。。

然后题目里一大段不自然的文字大概是说。。
1. 防御方的策略是贪心的。。（只要有钱就封杀直到没钱。。
2. 排除一些 bug 情况。。比如如果游戏途中某个位置进攻方占领了，它还可以向更左边的位置进军。。

。。。
（于是这个题读懂以后基本算法就已经给你了。。（为毛我感觉大家做法和我都不一样 0w0 。。。
。。按 ai 对位置进行排序。。（注意最后一个位置的价值是没有意义的。。用 0 替代。。
。。之后二分判定。。（。。从大到小。。遇到我们要的格子时暂跳过。。留到最后一回合。。。
。之后再从左到右扫描一遍找到第一个 ≥ 这个值的位置即可。。。）

Problem C. Fools and Roads:
给定一颗 n 个结点的树，以及 m 对访问信息。
问每条边被经过了多少次。。

Problem D. Metro Scheme:
给定一个地铁图。。。（。地铁分两类。。A 类线形。。B 类环形。。）
。。满足图是一个仙人掌图。。（。一个点最多只可能在一个环上。。）
。问形成这个图最多和最少需要几条地铁线呢。。

Problem E. Thwarting Demonstrations:
给定一个长度为 n 的数组，问在所有区间和之中 (。。共 C(n, 2) 组)。。
第 k 大的是多少。
(.. n <= 10^5 .. .)

Analysis:

Problem C. Fools and Roads:
。。动态树。（。类似去年多校的这题。。
。轻重链树链剖分。。或者 LCA() + DFS() 都可行。。）

Problem D. Metro Scheme:
。。貌似最多的就是边数。。于是最小的怎么求。。0w0？。。
我就去看了一眼 bjin 的代码。。发现只要先统计下欧拉路径的数目。。再在原图上找环就行了。。。
前者统计下奇数度定点数目 / 2 。。。后者可以直接在图上缩环。。0w0。。复杂度 O(n)。。。

Problem E. Thwarting Demonstrations:
二份答案判定，则子问题为，大于等于 x 的区间和的数量超过 k 吗？
这个经典的子问题解决办法有很多，这里用实现最容易的树状数组。
大概是这个样子。。

bool f(LL x, LL k) {
    RST(C); REP(i, n){
        Add(lower_bound(a, a + n, s[i]) - a + 1, 1);
        k -= Sum(lower_bound(a, a + n, s[i+1] - x + 1) - a);
        if (k <= 0) return true;
    }
    return false;
}

。。。。

int G[26][26], n;

int main(){

    while (scanf("%d", &n) != EOF && n){

        string s; REP(i, n){
            cin >> s; int a = s[0] - 'a', b = s[SZ(s)-1] - 'a';
            REP(i, 26) if (G[i][a]) checkMax(G[i][b], G[i][a] + SZ(s));
            checkMax(G[a][b], SZ(s));
        }

        int ans = 0; REP(i, 26){
            checkMax(ans, G[i][i]);
        }

        cout << ans << endl;
    }
}

const int N = 100009;

int A[N], O[N]; LL B;
int n, k;

bool comp(int a, int b){
    return A[a] > A[b]  || A[a] == A[b] && a < b;
}

bool f(int x){

    x = O[x];

    int i = 0, t = k - 1; LL b = B;

    while (t){
        if (O[i] == x) ++i;
        b -= A[O[i]];
        ++i, --t;
    }

    return b < A[x];
}

int main(){

    RD(n, k); cin >> B; REP(i, n) RD(A[i]), O[i] = i; A[n-1] = 0;
    sort(O, O + n, comp);

    if (!f(0)){
        cout << n << endl;
        return 0;
    }

    int l = 0, r = n - 2;

    while (l < r){
        int m = (l + r + 1) / 2;
        if (f(m)) l = m;
        else r = m - 1;
    }

    REP(i, n) if (A[i] >= A[O[l]]){
        cout << i + 1 << endl;
        return 0;
    }
}

const int N = 100009, M = 2 * N;

int l[N], r[N], p[N], w0[N], w1[N], delay[N]; bool rt[N];
// Link-cut tree
int hd[N], nxt[M], a[M], b[M];
// Adjacent list

int n, ans;

#define lx l[x]
#define rx r[x]

// private:

inline void Inc(int x, int d){
    if (x == 0) return;
    w0[x] += d, w1[x] += d, delay[x] += d;
}

inline void Release(int x){
    if (x == 0) return;

    if (delay[x]){
        Inc(lx, delay[x]), Inc(rx, delay[x]);
        delay[x] = 0;
    }
}

inline void Update(int x){
    w1[x] = w0[x] + w1[lx] + w1[rx];
}

inline void Set(int l[], int y, int x){
    l[y] = x, p[x] = y;
}

#define z p[y]
inline void Rotate(int x){
    int y = p[x];

    if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x);
    else p[x] = z;

    Release(y), Release(x);

    if (x == l[y]) Set(l, y, rx), Set(r, x, y);
    else Set(r, y, lx), Set(l, x, y);

    if (rt[y]) rt[y] = false, rt[x] = true;
    Update(y);
}

inline void Splay(int x){
    while (!rt[x]) Rotate(x);
}

inline int Access(int x){
    int y = 0; do{
        Splay(x), Release(x);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
    return y;
}

// public:

void Query(int x, int y){
    Access(y), y = 0; do{
        Splay(x); Release(x); if (!p[x]) OT(w1[rx] + w1[y]);
        rt[rx] = true, rt[rx = y] = false; Update(x);
        x = p[y = x];

    } while (x);
}

void Modify(int x, int y, int w){
    Access(y); y = 0; do{
        Splay(x), Release(x); if (!p[x]) Inc(rx, w), Inc(y, w);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
}

#define v b[i]
inline void dfs(int u = 1){
    for(int i=hd[u];i;i=nxt[i]) if (!p[v]){
        p[v] = u, dfs(v);
    }
}


int main(){

#ifdef LOCAL
    //freopen("in01.txt", "r", stdin);
#endif

    FOR_C(i, 2, _RD(n) << 1){
        RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i];
        nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
        nxt[i] = hd[a[i]], hd[a[i]] = i;
    }

    FLC(rt, true), p[1] = -1, dfs(), p[1] = 0;

    int x, y; DO_C(RD()){
        RD(x, y); Modify(x, y, 1);
    }

    FOR(i, 1, n) Query(a[i<<1], b[i<<1]);
}

const int N = 100009;
VI adj[N];
int n, m, ans;

int main() {

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

    int a, b; RD(n, m); REP(i, m){
        RD(a, b), --a, --b, adj[a].PB(b), adj[b].PB(a);
    }

#define deg(x) SZ(adj[x])

    REP(i, n) if (deg(i)&1) ++ans;
    ans >>= 1;

    REP(i, n) if (deg(i) == 2){
        a = adj[i][0], b = adj[i][1];
        if (a == b){
            CLR(adj[a]);
            ++ans;
        }
        else {
            adj[a][adj[a][0] == i ? 0 : 1] = b;
            adj[b][adj[b][0] == i ? 0 : 1] = a;
        }
    }

    printf("%d %d\n", ans, m);
}

const int N = 100009;
int C[N]; LL s[N], a[N];
int n; LL k;

void Add(int x, int d){
    for (int i=x;i<=n;i+=low_bit(i)) C[i] += d;
}

LL Sum(int x){
    LL res = 0; for(int i=x;i;i^=low_bit(i)) res += C[i];
    return res;
}

bool f(LL x, LL k) {
    RST(C); REP(i, n){
        Add(lower_bound(a, a + n, s[i]) - a + 1, 1);
        k -= Sum(lower_bound(a, a + n, s[i+1] - x) - a);
        if (k <= 0) return true;
	}
	return false;
}

//((s[r] - s[l-1]) >= x)
//s[l-1] <= s[r] - x ...

int main() {

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d %I64d", &n, &k);
	//scanf("%d %lld", &n, &k);

	REP(i, n) s[i+1] = s[i] + RD();
    REP(i, n) a[i] = s[i]; sort(a, a + n);

	LL l = -1e14 - 1, r = 1e14 - 1;
	while (l <= r) {
		LL m = (l + r) / 2;
		if (f(m, k)) l = m + 1;
        else r = m - 1;
	}

	printf("%I64d\n", l);
	//printf("%lld\n", l - 1);
}