HNOI2017
（线段树、set）
手玩旋转操作（忽略手玩过程）可以发现：一次单旋对原树的变化实际上很小。
对于父子关系，单旋最小值会将\(Spaly\)上最小值变成原来根的父亲，将最小值的点右子树变为它父亲的左子树，单旋最大值相反；
对于\(dep\)的变化，单旋最小值时，除了最小值点和它的右子树，其他点的\(dep+1\)。注意到\(key\)在一段区间的点\(dep\)同时变化，故离散化\(key\)，线段树维护\(dep\)。而删除根意味着所有点的\(dep-1\)，也可以线段树维护。
对于插入操作，每一次找到中序遍历的前驱后继，它们在\(Spaly\)上一定有一个是另一个的祖先。那么我们去找深度较深的点，然后接在上面。中序遍历维护直接用\(set\)，对于每一个点维护父亲和儿子，每一次插入、旋转和删除时一并维护。
#include#include #include #include #include #include #include #include #include #include //This code is written by Itstusing namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a;}const int MAXN = 1e5 + 7;int qry[MAXN] , nd[MAXN] , lsh[MAXN] , fa[MAXN] , ch[MAXN][2];int M , cnt , rt;set < int > spaly;set < int > :: iterator it;namespace segTree{ int dep[MAXN << 2] , mrk[MAXN << 2];#define mid ((l + r) >> 1)#define lch (x << 1)#define rch (x << 1 | 1) void mark(int x , int num){ mrk[x] += num; dep[x] += num; } inline void pushdown(int x){ mark(lch , mrk[x]); mark(rch , mrk[x]); mrk[x] = 0; } void set(int x , int l , int r , int tar , int num){ if(l == r){ dep[x] = num; return; } pushdown(x); if(mid >= tar) set(lch , l , mid , tar , num); else set(rch , mid + 1 , r , tar , num); } void add(int x , int l , int r , int L , int R , int num){ if(l >= L && r <= R){ mark(x , num); return; } pushdown(x); if(mid >= L) add(lch , l , mid , L , R , num); if(mid < R) add(rch , mid + 1 , r , L , R , num); } int query(int x , int l , int r , int tar){ if(l == r) return dep[x]; pushdown(x); if(mid >= tar) return query(lch , l , mid , tar); return query(rch , mid + 1 , r , tar); }}using segTree::add;using segTree::query;inline int insert(int x){ int dep = 0; if(spaly.empty()) segTree::set(1 , 1 , cnt , rt = x , dep = 1); else{ it = spaly.lower_bound(x); if(it != spaly.end() && !ch[*it][0]) segTree::set(1 , 1 , cnt , ch[fa[x] = *it][0] = x , dep = query(1 , 1 , cnt , *it) + 1); else{ --it; segTree::set(1 , 1 , cnt , ch[fa[x] = *it][1] = x , dep = query(1 , 1 , cnt , *it) + 1); } } spaly.insert(x); return dep;}inline int rot_min(){ int t = *spaly.begin(); int dep = query(1 , 1 , cnt , t); segTree::set(1 , 1 , cnt , t , 1); if(rt != t){ add(1 , 1 , cnt , fa[t] , cnt , 1); fa[ch[t][1]] = fa[t]; ch[fa[t]][0] = ch[t][1]; fa[t] = 0; ch[t][1] = rt; rt = fa[rt] = t; } return dep;}inline int rot_max(){ int t = *--spaly.end(); int dep = query(1 , 1 , cnt , t); segTree::set(1 , 1 , cnt , t , 1); if(rt != t){ add(1 , 1 , cnt , 1 , fa[t] , 1); fa[ch[t][0]] = fa[t]; ch[fa[t]][1] = ch[t][0]; fa[t] = 0; ch[t][0] = rt; rt = fa[rt] = t; } return dep;}inline int del_min(){ int dep = rot_min(); add(1 , 1 , cnt , 1 , cnt , -1); fa[rt = ch[rt][1]] = 0; spaly.erase(spaly.begin()); return dep;}inline int del_max(){ int dep = rot_max(); add(1 , 1 , cnt , 1 , cnt , -1); fa[rt = ch[rt][0]] = 0; spaly.erase(--spaly.end()); return dep;}int main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout);#endif M = read(); for(int i = 1 ; i <= M ; ++i) if((qry[i] = read()) == 1) nd[++cnt] = read(); for(int i = 1 ; i <= cnt ; ++i) lsh[i] = nd[i]; sort(lsh + 1 , lsh + cnt + 1); for(int i = 1 ; i <= cnt ; ++i) nd[i] = lower_bound(lsh + 1 , lsh + cnt + 1 , nd[i]) - lsh; int Cnt = 0; for(int i = 1 ; i <= M ; ++i) switch(qry[i]){ case 1: printf("%d\n" , insert(nd[++Cnt])); break; case 2: printf("%d\n" , rot_min()); break; case 3: printf("%d\n" , rot_max()); break; case 4: printf("%d\n" , del_min()); break; case 5: printf("%d\n" , del_max()); break; } return 0;}
（单调栈、线段树）
跟是同一个做法
将询问离线，按照右端点排序，然后把数从左往右一个一个加进去，用线段树维护每一个左端点的贡献。一个区间产生贡献至少要求它两端的最大值比中间所有值的最大值要大，不难想到可以用单调栈维护贡献的产生。那么当某一个数\(a_i\)加入到单调栈中时，单调栈第\(j\)个位置的贡献有\(3\)种可能：
①\(a_j < a_i\)，意味着区间\([a_j,a_i]\)可以产生\(p_1\)的贡献；
②\(a_j > a_i\)且\(a_{j + 1} < a_i\)，意味着区间\([a_j,a_i]\)可以产生\(p_1\)的贡献且区间\([k,a_i] (k > a_j , k \neq a_l , l > j)\)可以产生\(p_2\)的贡献
③\(a_j > a_i\)且\(a_{j+1} > a_i\)，意味着区间\([a_j,a_i]\)可以产生\(p_2\)的贡献
拿两个线段树，一个维护不在栈内的数的贡献，一个维护在栈内的数的贡献。①是单点修改，③是栈对应线段树上的区间修改，而②不是很好做。考虑将①变成产生\(p_1 - p_2\)的贡献，将②变成区间\([k,i] , k > a_j\)可以产生\(p_2\)的贡献，就是一个区间修改。每一次弹栈的时候就把弹栈的元素在栈对应的线段树上的贡献丢到不在栈内的线段树中，答案就把两个线段树的答案加一起。
#include#include #include #include #include #include //This code is written by Itstusing namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a;}const int MAXN = 2e5 + 3;#define ll long long#define mid ((l + r) >> 1)#define lch (x << 1)#define rch (x << 1 | 1)namespace segTree1{ ll sum[MAXN << 2] , mrk[MAXN << 2]; inline void pushup(int x) {sum[x] = sum[lch] + sum[rch];} inline void mark(int x , int l , int r , ll num){ sum[x] += (r - l + 1) * num; mrk[x] += num; } inline void pushdown(int x , int l , int r){ mark(lch , l , mid , mrk[x]); mark(rch , mid + 1 , r , mrk[x]); mrk[x] = 0; } void modify1(int x , int l , int r , int L , int R , int num){ if(l >= L && r <= R){ mark(x , l , r , num); return; } pushdown(x , l , r); if(mid >= L) modify1(lch , l , mid , L , R , num); if(mid < R) modify1(rch , mid + 1 , r , L , R , num); pushup(x); } ll query1(int x , int l , int r , int L , int R){ if(l >= L && r <= R) return sum[x]; pushdown(x , l , r); ll sum = 0; if(mid >= L) sum += query1(lch , l , mid , L , R); if(mid < R) sum += query1(rch , mid + 1 , r , L , R); return sum; }}using segTree1::modify1; using segTree1::query1;namespace segTree2{ ll sum[MAXN << 2] , mrk[MAXN << 2]; inline void pushup(int x) {sum[x] = sum[lch] + sum[rch];} inline void mark(int x , int l , int r , ll num){ sum[x] += (r - l + 1) * num; mrk[x] += num; } inline void pushdown(int x , int l , int r){ mark(lch , l , mid , mrk[x]); mark(rch , mid + 1 , r , mrk[x]); mrk[x] = 0; } void modify2(int x , int l , int r , int L , int R , int num){ if(l >= L && r <= R){ mark(x , l , r , num); return; } pushdown(x , l , r); if(mid >= L) modify2(lch , l , mid , L , R , num); if(mid < R) modify2(rch , mid + 1 , r , L , R , num); pushup(x); } ll query2(int x , int l , int r , int L , int R){ if(l >= L && r <= R) return sum[x]; pushdown(x , l , r); ll sum = 0; if(mid >= L) sum += query2(lch , l , mid , L , R); if(mid < R) sum += query2(rch , mid + 1 , r , L , R); return sum; } void clear(int x , int l , int r , int tar){ if(l == r){ sum[x] = mrk[x] = 0; return; } pushdown(x , l , r); mid >= tar ? clear(lch , l , mid , tar) : clear(rch , mid + 1 , r , tar); pushup(x); }}using segTree2::modify2; using segTree2::query2; using segTree2::clear;struct query{ int l , r , ind; bool operator <(const query a)const{ return r < a.r; }}que[MAXN];int arr[MAXN] , stk[MAXN];ll ans[MAXN];int N , M , top , P1 , P2;int main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout);#endif N = read(); M = read(); P1 = read(); P2 = read(); for(int i = 1 ; i <= N ; ++i) arr[i] = read(); for(int i = 1 ; i <= M ; ++i){ que[i].l = read(); que[i].r = read(); que[i].ind = i; } sort(que + 1 , que + M + 1); for(int i = 1 ; i <= M ; ++i){ while(que[i - 1].r < que[i].r){ ++que[i - 1].r; while(top && arr[que[i - 1].r] > arr[stk[top]]){ modify1(1 , 1 , N , stk[top] , stk[top] , query2(1 , 1 , N , top , top) + P1 - P2); clear(1 , 1 , N , top--); } if(top){ modify2(1 , 1 , N , top , top , P1 - P2); modify2(1 , 1 , N , 1 , top , P2); } if(stk[top] + 1 <= que[i - 1].r - 1) modify1(1 , 1 , N , stk[top] + 1 , que[i - 1].r - 1 , P2); stk[++top] = que[i - 1].r; } ans[que[i].ind] = query1(1 , 1 , N , que[i].l , que[i].r) + query2(1 , 1 , N , lower_bound(stk + 1 , stk + top + 1 , que[i].l) - stk , top); } for(int i = 1 ; i <= M ; ++i) cout << ans[i] << '\n'; return 0;}
（FFT）
\(\sum\limits_{i=1} ^ N (x_i - y_i + m)^2 = \sum\limits_{i=1}^N (x_i^2 + y_i^2) + Nm^2 + 2m\sum\limits_{i=1}^N(x_i - y_i) - 2 \sum\limits_{i=1}^N x_iy_i\)
手串旋转只会影响到\(\sum x_iy_i\)的值，而式子是一个卷积的形式，故用FFT求\(\min \{\sum x_iy_i\}\)。具体来说把\(x\)倍长、\(y\)翻转再\(FFT\)，其中某些项就是这个卷积的值。
然后原式就是一个关于\(m\)的二次函数，初中公式求解。注意你需要取到的\(m\)值应该是离对称轴最近的整点而不是直接向上或者向下取整。
#include#define ld long double//This code is written by Itstusing namespace std;inline int read(){ int a = 0; bool f = 0; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = 1; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << 3) + (a << 1) + (c ^ '0'); c = getchar(); } return f ? -a : a;}const int MAXN = 270000;struct comp{ ld x , y; comp(ld _x = 0 , ld _y = 0){ x = _x; y = _y; } comp operator +(comp a){ return comp(x + a.x , y + a.y); } comp operator -(comp a){ return comp(x - a.x , y - a.y); } comp operator *(comp a){ return comp(x * a.x - y * a.y , x * a.y + y * a.x); } }a[MAXN] , b[MAXN];int dir[MAXN] , need , N , M;const ld pi = acos(-1);void FFT(comp* a , int type){ for(int i = 0 ; i < need ; ++i) if(dir[i] > i) swap(a[i] , a[dir[i]]); for(int i = 1 ; i < need ; i <<= 1){ comp wn(cos(pi / i) , type * sin(pi / i)); for(int j = 0 ; j < need ; j += i << 1){ comp w(1 , 0); for(int k = 0 ; k < i ; ++k , w = w * wn){ comp x = a[j + k] , y = a[i + j + k] * w; a[j + k] = x + y; a[i + j + k] = x - y; } } }}int main(){#ifndef ONLINE_JUDGE freopen("3723.in" , "r" , stdin); //freopen("3723.out" , "w" , stdout);#endif N = read(); M = read(); int B = 0 , C = 0; for(int i = 0 ; i < N ; ++i){ a[i].x = read(); C += a[i].x * a[i].x; B += a[i].x; } for(int i = 0 ; i < N ; ++i){ b[N - i - 1].x = b[(N << 1) - i - 1].x = read(); C += b[N - i - 1].x * b[N - i - 1].x; B -= b[N - i - 1].x; } B <<= 1; need = 1; while(need <= N * 3) need <<= 1; for(int i = 1 ; i < need ; ++i) dir[i] = (dir[i >> 1] >> 1) | (i & 1 ? need >> 1 : 0); FFT(a , 1); FFT(b , 1); for(int i = 0 ; i < need ; ++i) a[i] = a[i] * b[i]; FFT(a , -1); int maxN = 0; for(int i = N - 1 ; i - N + 1 < N ; ++i) maxN = max(maxN , (int)(a[i].x / need + 0.5)); int t; if(B / -2.0 / N > 0) t = B / -2.0 / N + 0.5; else t = B / -2.0 / N - 0.5; cout << N * t * t + B * t + C - 2 * maxN; return 0;}
（DP、BFS）
发现回复信心值和怼大佬是独立的，那就分开算。
我们要留尽可能多的时间怼大佬，所以设\(dp_{i,j}\)表示第\(i\)天信心值为\(j\)时最小恢复天数，那么最多的怼大佬天数是\(D = \max\limits_i \max\limits_j i - dp_{i,j}\)
考虑怼大佬的方案。用\(BFS+Hash\)暴力求出所有怼一次大佬能降低的信心值的数量和对应最短天数，天数不多所以状态量不大。
对于不怼大佬和只怼一次的情况比较好算，比较麻烦的是怼两次的情况。
假设两次怼大佬的值为\(f_a\)和\(f_b\)，分别需要\(d_a\)和\(d_b\)天，那么需要满足\(f_a + f_b \leq hp\)且\(f_a - d_a + f_b - d_b + D \geq hp\)
故将所有方案组\((f , d)\)按\(f\)从小到大排序，维护两个指针\(i,j\)，\(i\)从后往前扫，\(j\)跟着\(i\)从前往后扫，并一直满足\(f_i + f_j \leq hp\)。此时\(f_i , d_i , D , hp\)已知，只需求出对于所有\(j\)最大的\(f_j - d_j\)，而在\(i\)指针向前移动的过程\(j\)单调，所以直接在\(j\)移动的过程中维护\(1\)到\(j\)的组中\(f - d\)的最大值。
#include#include #include #include #include #include #include #include #include #include
（计算几何、nan）
太\(\large\color{red}{nan}\)了不会
（ExLucas）
不妨把正面看做\(1\)、反面看做\(0\)，然后把硬币排开，就变成了一个长度为\(a+b\)的二进制数。然后题目变成了一个数数问题。
首先考虑\(a=b\)的情况。对于一个\(A\)胜利的情况，将所有硬币翻转，就变成了一个\(B\)胜利的情况；而平局翻转之后是平局。所以答案是\(\frac{2^{a + b} - cnt_{tie}}{2}\)，\(cnt_{tie}\)是平局的数量\(=\sum\limits_{i=0}^a (C_{a}^i)^2 = \sum\limits_{i=0}^a C_{a}^i \times C_{a}^{a - i} = C_{2a}^a\)。最后一步转化的意义是：将\(2a\)个数分成两份，每份\(a\)个数，在第一份中取出\(i \in [0,a]\)个数，在第二份中取出\(a-i\)个数，等价于在\(2a\)个数中选出\(a\)个数。
考虑\(a > b\)的情况。此时对于一个\(B\)胜利或平局的情况，将所有硬币翻转就会变成一个\(A\)胜利的情况，而存在\(A\)胜利的情况翻转后仍是\(A\)胜利，所以答案是\(\frac{2^{a+b} + cnt_{win}}{2}\)，其中\(cnt_{win}\)是\(A\)胜利、且翻转之后还是\(A\)胜利的情况。
对于某一个能对\(cnt_{win}\)产生贡献的情况，设\(A\)有\(cntA\)个硬币向上，\(B\)有\(cntB\)个硬币向上，那么有\(cntA > cntB\)且\(a - cntA > b - cntB\)，可以归为\(a - b > cntA - cntB > 0\)
然后枚举\(cntB\)与\(cntA - cntB\)，\(cnt_{win} = \sum\limits_{i=0}^{b} \sum\limits_{j=1}^{a - b - 1} C_b^i C_a^{i + j} = \sum\limits_{j=1}^{a - b - 1} \sum\limits_{i=0}^b C_b^{b - i} C_{a}^{i + j} = \sum\limits_{j=1}^{a - b - 1} C_{a + b}^{b + j}\)，最后一步跟\(a=b\)的最后一步意义是一致的。
所以我们需要计算一些组合数\(\mod 10^K\)的值，直接上\(ExLucas\)。一些细节写在下面code里
#include#include #include #include #include #include #include #include #include #define INF 1e18//This code is written by Itstusing namespace std;#define int long longinline int read(){ int a = 0; char c = getchar(); while(!isdigit(c) && c != EOF) c = getchar(); if(c == EOF) exit(0); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a;}int JC[6][10] , times[6][10];vector < int > ans[6][10];int A , B , K , P;void init(){//一切可以预处理的最好都预处理 times[2][0] = times[5][0] = 1; for(int i = 1 ; i <= 9 ; ++i){ times[2][i] = times[2][i - 1] * 2; times[5][i] = times[5][i - 1] * 5; ans[2][i].push_back(1); for(int j = 1 ; j <= times[2][i] ; ++j) ans[2][i].push_back(ans[2][i][j - 1] * (j & 1 ? j : 1) % times[2][i]); JC[2][i] = ans[2][i][times[2][i]]; ans[5][i].push_back(1); for(int j = 1 ; j <= times[5][i] ; ++j) ans[5][i].push_back(ans[5][i][j - 1] * (j % 5 ? j : 1) % times[5][i]); JC[5][i] = ans[5][i][times[5][i]]; }}inline int poww(int a , int b , int P = INF){ int times = 1; while(b){ if(b & 1) times = times * a % P; a = a * a % P; b >>= 1; } return times;}inline int jc(int x , int p , int k){ if(x == 0) return 1; int t = times[p][k] , tms = poww(JC[p][k] , x / t , t) * ans[p][k][x % t] % t;//预处理的东西多了这里就可以直接算答案，不需要枚举 return tms * jc(x / p , p , k) % t;//最开始写ExLucas没递归可还行}void exgcd(int a , int b , int &x , int &y){ !b ? (x = 1 , y = 0) : (exgcd(b , a % b , y , x) , y -= a / b * x);}inline int inv(int a , int b){ a %= b; int x , y; exgcd(a , b , x , y); return (x + b) % b;}inline int calc(int a , int b , int p , int k){ int A = a , B = b , c = a - b , C = c , t = times[p][k] , cnt = 0; while(A) cnt += A /= p; while(B) cnt -= B /= p; while(C) cnt -= C /= p; if(cnt >= k)//先算cnt快到飞起 return 0; A = jc(a , p , k); B = jc(b , p , k); C = jc(c , p , k); return times[p][cnt] * A % t * inv(B , t) % t * inv(C , t) % t;}inline int CRT(int x , int y){ return (times[5][K] * inv(times[5][K] , times[2][K]) % P * x + times[2][K] * inv(times[2][K] , times[5][K]) % P * y) % P;}inline int C(int a , int b){ return CRT(calc(a , b , 2 , K) , calc(a , b , 5 , K));}void output(int x){ string s; while(x){ s = (char)(x % 10 + '0') + s; x /= 10; } while(s.size() < K) s = '0' + s; cout << s << endl;}signed main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout);#endif init(); while(A = read()){ B = read(); K = read(); P = 1; for(int i = 1 ; i <= K ; ++i) P = P * 10; int sum = 0; if(A == B)//C(2A,A)没法除2怎么办？注意到C(2A,A)=C(2A-1,A-1)+C(2A-1,A)=2C(2A-1,A)，所以算出C(2A-1,A)就行了 sum = (poww(2 , A + B - 1 , P) - C(2 * A - 1 , A) + P) % P; else{ sum = poww(2 , A + B - 1 , P); for(int i = B + 1 ; i < A + B - i ; ++i)//因为C(A+B,B+1)=C(A+B,A-1),C(A+B,B+2)=C(A+B,A-2)……所以这里只需算一半 sum = (sum + C(A + B , i)) % P; if(!(A + B & 1)) sum = (sum + C(A + B - 1 , (A + B) / 2)) % P; } output(sum); } return 0;}