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