Day1
4825: [Hnoi2017]单旋
注意到二叉查找树的一个性质：其中序遍历就是所有元素按权值排序的顺序。
所以我们可以离线地把这棵树的中序遍历求出来。然后我们在插入的时候就可以用一个set来维护前驱后继，这样就可以维护出整棵树的形态。
接着我们发现将最大、最小单旋到根后，一定会有一边儿子是空的，并且剩下的子树的深度+1。于是我们就只要支持单点修改、区间加、单点查询的数据结构即可。树状数组就好了。
然后树的形态维护的时候大力判断一下就好啦。
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm> #define R register
#define P std::pair<int, int>
#define mkp std::make_pair
#define maxn 100010
#define fir first
#define sec second
int v[maxn], ch[maxn][], fa[maxn], tot;
std::set<P> s;
int q[maxn];
int dfn[maxn], inv[maxn], timer, pos[maxn], ltag;
int ql, qr;
int hash[maxn];
int bt[maxn];
void add(R int x, R int val) {for (; x <= tot; x += x & -x) bt[x] += val;}
int query(R int x) {R int ret = ; for (; x; x -= x & -x) ret += bt[x]; return ret;}
void modify(R int l, R int r, R int v)
{
// printf("l = %d r = %d v = %d\n", l, r, v);
add(l, v); add(r + , -v);
}
int main()
{
R int n, root; scanf("%d", &n);
s.insert(mkp(, ));
s.insert(mkp(1e9 + , ));
for (R int i = ; i <= n; ++i)
{
R int opt; scanf("%d", &opt); q[i] = opt;
if (opt == ) {R int key; scanf("%d", &key); v[++tot] = key; hash[tot] = key;}
}
std::sort(hash + , hash + tot + );
for (R int i = ; i <= n; ++i) dfn[i] = std::lower_bound(hash + , hash + tot + , v[i]) - hash;
for (R int i = , nw = ; i <= n; ++i)
{
R int opt = q[i];
if (opt == )
{
R P now = mkp(v[++nw], nw);
R P prev = *(--s.upper_bound(now)), next = *s.upper_bound(now);
s.insert(now);
if (prev.sec && !ch[prev.sec][])
{
ch[prev.sec][] = nw;
fa[nw] = prev.sec;
}
else if (next.sec && !ch[next.sec][])
{
ch[next.sec][] = nw;
fa[nw] = next.sec;
}
!fa[nw] ? root = nw : ; R int dep;
printf("%d\n", dep = fa[nw] ? query(dfn[fa[nw]]) + : );
modify(dfn[nw], dfn[nw], dep - query(dfn[nw]));
}
else if (opt == )
{
R P xmin = *(++s.begin()); R int xc = xmin.sec;
printf("%d\n", query(dfn[xc]));
// printf("fa %d\n", fa[xc]);
modify(!fa[xc] ? tot + : dfn[fa[xc]], tot, );
modify(dfn[xc], dfn[xc], - query(dfn[xc])); if (root != xc)
{
ch[fa[xc]][] = ch[xc][];
fa[ch[xc][]] = fa[xc];
fa[root] = xc;
ch[xc][] = root;
root = xc;
fa[xc] = ;
}
}
else if (opt == )
{
R P xmax = *(++s.rbegin()); R int xc = xmax.sec;
printf("%d\n", query(dfn[xc]));
modify(, !fa[xc] ? : dfn[fa[xc]], );
modify(dfn[xc], dfn[xc], - query(dfn[xc])); if (root != xc)
{
ch[fa[xc]][] = ch[xc][];
fa[ch[xc][]] = fa[xc];
fa[root] = xc;
ch[xc][] = root;
root = xc;
fa[xc] = ;
}
}
else if (opt == )
{
R P xmin = *(++s.begin()); R int xc = xmin.sec;
printf("%d\n", query(dfn[xc]));
modify(dfn[xc] + , !fa[xc] ? tot : dfn[fa[xc]] - , -); xc == root ? fa[root = ch[xc][]] = :
(ch[fa[xc]][] = ch[xc][],
fa[ch[xc][]] = fa[xc]);
s.erase(xmin);
}
else
{
R P xmax = *(++s.rbegin()); R int xc = xmax.sec;
// printf("max %d %d\n", xc, fa[xc]);
printf("%d\n", query(dfn[xc]));
modify(!fa[xc] ? : dfn[fa[xc]] + , dfn[xc] - , -); xc == root ? fa[root = ch[xc][]] = :
(ch[fa[xc]][] = ch[xc][],
fa[ch[xc][]] = fa[xc]);
s.erase(xmax);
}
}
return ;
}
/*
6
1 1
1 2
1 4
4
2
5
性质：二叉查找树的子树的权值对应的是一个区间。并且有且仅有所有子树内的点在这个区间内。
*/
D1T1
4826: [Hnoi2017]影魔
第1种的贡献可以用单调栈算。第2种的贡献没那么好算，所以我们来考虑1+2的贡献。1+2的贡献可以转为二维偏序，用排序+线段树来搞。
#include <cstdio>
#include <algorithm>
#include <cstring> #define R register
#define maxn 200010
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
inline int F()
{
R char ch; R int cnt;
while (ch = getchar(), ch < '' || ch > '') ;
cnt = ch - '';
while (ch = getchar(), ch >= '' && ch <= '') cnt = cnt * + ch - '';
return cnt;
}
typedef long long ll;
struct Query {
int l, r;
} q[maxn];
struct Chain {
Chain *next;
int id;
} *last[maxn], mem[maxn], *tot = mem;
struct Opt {
int x, id, type;
inline bool operator < (const Opt &that) const {return x < that.x;}
} op[maxn << ];
int ans1[maxn]; ll ans2[maxn];
int st[maxn], top, a[maxn];
int ql, qr;
ll tr[maxn << ], tag[maxn << ];
inline void pushdown(R int o, R int l, R int r, R int mid)
{
if (tag[o])
{
tag[o << ] += tag[o];
tag[o << | ] += tag[o];
tr[o << ] += 1ll * tag[o] * (mid - l + );
tr[o << | ] += 1ll * tag[o] * (r - mid);
tag[o] = ;
}
}
inline void update(R int o) {tr[o] = tr[o << ] + tr[o << | ];}
void modify(R int o, R int l, R int r)
{
if (ql <= l && r <= qr)
{
++tag[o]; tr[o] += (r - l + );
return ;
}
R int mid = l + r >> ;
pushdown(o, l, r, mid);
if (ql <= mid) modify(o << , l, mid);
if (mid < qr) modify(o << | , mid + , r);
update(o);
}
ll query(R int o, R int l, R int r)
{
if (ql <= l && r <= qr) return tr[o];
R int mid = l + r >> ;
R ll ret = ;
pushdown(o, l, r, mid);
if (ql <= mid) ret += query(o << , l, mid);
if (mid < qr) ret += query(o << | , mid + , r);
return ret;
}
int bt[maxn], n, lef[maxn], rig[maxn], r[maxn], Fa[maxn];
int Find(R int x) {return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);}
inline void add(R int x) {for (; x <= n; x += x & -x) ++bt[x];}
inline int query(R int x) {R int ret = ; for (; x; x -= x & -x) ret += bt[x]; return ret;}
int main()
{
n = F(); R int m = F(), p1 = F(), p2 = F();
for (R int i = ; i <= n; ++i) a[i] = F(), r[a[i]] = i, Fa[i] = lef[i] = rig[i] = i;
R int opcnt = ;
for (R int i = ; i <= m; ++i)
{
q[i] = (Query) {F(), F()};
*++tot = (Chain) {last[q[i].r], i}; last[q[i].r] = tot;
op[++opcnt] = (Opt) {q[i].l - , i, -};
op[++opcnt] = (Opt) {q[i].r, i, };
} memset(bt, , (n + ) << ); top = ;
for (R int i = ; i <= n; ++i)
{
R int rr = i - ;
while (top && a[st[top]] < a[i]) add(st[top--]);
if (top) add(st[top]);
st[++top] = i;
for (R Chain *iter = last[i]; iter; iter = iter -> next)
ans1[iter -> id] += query(q[iter -> id].r) - query(q[iter -> id].l - );
} std::sort(op + , op + opcnt + );
for (R int i = ; i <= n; ++i)
{
R int ps = r[i], f1;
if (ps != && a[ps - ] < i) lef[ps] = lef[f1 = Find(ps - )], Fa[f1] = ps;
if (ps != n && a[ps + ] < i) rig[ps] = rig[f1 = Find(ps + )], Fa[f1] = ps;
}
R int p = ;
while (op[p].x == ) ++p;
for (R int i = ; i <= n; ++i)
{
// printf("%d %d\n", lef[i], rig[i]);
ql = lef[i]; qr = rig[i];
modify(, , n);
while (op[p].x == i)
{
ql = q[op[p].id].l; qr = q[op[p].id].r;
ans2[op[p].id] += op[p].type * query(, , n);
++p;
}
}
for (R int i = ; i <= m; ++i) printf("%lld\n", 1ll * ans1[i] * p1 + (ans2[i] - (q[i].r - q[i].l + ) - ans1[i]) * p2);
return ;
}
/*
9 4
12 5
2 0
5 1
5 2
30
39
4
13
16 */
D1T2
4827: [Hnoi2017]礼物
把式子拆开完就是一个卷积和二次函数的形式，二次函数用对称轴公式来算，卷积用FFT来算。
#include <cstdio>
#include <algorithm>
#include <cmath> #define R register
#define maxn 262145
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
typedef double db;
const db pi = acos(-);
struct Complex {
db x, y;
inline Complex operator - (const Complex &that) const {return (Complex) {x - that.x, y - that.y};}
inline Complex operator * (const Complex &that) const {return (Complex) {x * that.x - y * that.y, x * that.y + that.x * y};}
inline void operator += (const Complex &that) {x += that.x; y += that.y;}
} w[maxn << ];
int N;
void init()
{
R int h = N >> ;
for (R int i = ; i < N; ++i) w[i + h] = (Complex) {cos( * pi / N * i), sin( * pi / N * i)};
for (R int i = h; i--; ) w[i] = w[i << ];
}
void bit_reverse(R Complex *a, R Complex *b)
{
for (R int i = ; i < N; ++i) b[i] = a[i];
for (R int i = , j = ; i < N; ++i)
{
i > j ? std::swap(b[i], b[j]), : ;
for (R int l = N >> ; (j ^= l) < l; l >>= ) ;
}
}
void dft(R Complex *a)
{
for (R int l = , m = ; m < N; l <<= , m <<= )
for (R int i = ; i < N; i += l)
for (R int j = ; j < m; ++j)
{
R Complex tmp = a[i + j + m] * w[j + m];
a[i + j + m] = a[i + j] - tmp;
a[i + j] += tmp;
}
}
Complex a[maxn], b[maxn], c[maxn], ta[maxn], tb[maxn], tc[maxn];
int main()
{
R int n, m, ans = 0x7fffffff, ret = , sum = ; scanf("%d%d", &n, &m);
for (R int i = ; i < n; ++i) scanf("%lf", &a[i].x), sum -= a[i].x;
for (R int i = ; i < n; ++i) scanf("%lf", &b[i].x), sum += b[i].x;
std::reverse(b, b + n);
for (R int i = ; i < n; ++i) b[i + n] = b[i];
for (N = ; N < (n << ); N <<= );
init();
R int ccc = round((db) sum / n); for (R int i = ; i < n; ++i) a[i].x += ccc, ret += a[i].x * a[i].x + b[i].x * b[i].x;
// printf("%d %d\n", ccc, ret);
bit_reverse(a, ta);
bit_reverse(b, tb);
dft(ta); dft(tb);
for (R int i = ; i < N; ++i) c[i] = ta[i] * tb[i];
std::reverse(c + , c + N);
bit_reverse(c, tc); dft(tc);
// for (R int i = 0; i < N; ++i) printf("%lf %lf\n", tc[i].x, tc[i].y);
for (R int i = ; i < n; ++i) cmin(ans, (int) ret - ( * tc[i + n].x / N)); printf("%d\n", ans);
return ;
}
D1T3
Day2
4828: [Hnoi2017]大佬
玄学搜索题。搜索出来完用双指针扫一扫。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <bitset> #define R register
#define maxn 110
int a[maxn], w[maxn];
int f[maxn][maxn];
const int oo = 1e8;
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
const int mod = ;
typedef long long ll;
struct Queue {
int step, level, f;
} q[];
struct Hash {
Hash *next;
ll key;
} *last[mod], mem[mod], *tot = mem;
inline ll hash_key(R int a, R int b)
{
return 1ll * b * + a;
}
inline bool insert(R int a, R int b)
{
R ll key = hash_key(a, b);
R int pos = key % mod;
for (R Hash *iter = last[pos]; iter; iter = iter -> next)
if (iter -> key == key) return ;
*++tot = (Hash) {last[pos], key}; last[pos] = tot;
return ;
}
struct Data {
int f, s;
inline bool operator < (const Data &that) const {return f < that.f;}
} st[maxn * maxn * maxn];
int scnt, qu[];
int main()
{
R int n, m, mc; scanf("%d%d%d", &n, &m, &mc);
for (R int i = ; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = ; i <= n; ++i) scanf("%d", &w[i]);
memset(f, -, sizeof (f));
f[][mc] = ;
for (R int i = ; i <= n; ++i)
{
for (R int j = a[i]; j <= mc; ++j)
cmax(f[i][j - a[i]], f[i - ][j] + ),
cmax(f[i][dmin(j - a[i] + w[i], mc)], f[i - ][j]);
}
R int Day = -;
for (R int j = ; j <= n; ++j) for (R int i = ; i <= mc; ++i) cmax(Day, f[j][i]);
R int oo = ;
for (R int i = ; i <= m; ++i) scanf("%d", &qu[i]), cmax(oo, qu[i]); R int head = , tail = ;
q[] = (Queue) {, , };
while (head < tail)
{
R Queue now = q[++head];
if (insert(, now.f)) st[++scnt] = (Data) {now.f, now.step + };
if (now.step >= Day - ) continue;
if (now.level > && oo / now.level < now.f) continue;
if (insert(now.level + , now.f)) q[++tail] = (Queue) {now.step + , now.level + , now.f}; if (1ll * now.f * now.level <= oo && now.f > )
{
if (insert(now.level, now.f * now.level))
q[++tail] = (Queue) {now.step + , now.level, now.f * now.level};
}
}
st[++scnt] = (Data) {, };
std::sort(st + , st + scnt + );
for (R int _ = ; _ <= m; ++_)
{
R int c = qu[_], flag = ;
if (Day <= ) {puts(""); continue;}
if (c <= Day) {puts(""); continue;}
R int j = , mx = -oo * ;
for (R int i = scnt; i; --i)
{
for (; j < scnt && st[j + ].f + st[i].f <= c; ++j, cmax(mx, st[j].f - st[j].s));
if (mx + st[i].f - st[i].s >= c - Day)
{
flag = ;
break;
}
}
printf("%d\n", flag);
}
return ;
}
/*
10 20 100
22 18 15 16 20 19 33 15 38 49
92 14 94 92 66 94 1 16 90 51
4
5
9
338
5222
549
7491
9
12
3288
3
1
2191
833
3
6991
2754
3231
360
6 1
1
1
0
0
0
0
1
1
0
1
1
0
0
1
0
0
0
0
1
*/
D2T1
4829: [Hnoi2017]队长快跑
看起来很nan，没去看。听说是一道不可做题。
4830: [Hnoi2017]抛硬币
广义Lucas定理。普通的Lucas一般指用于质数，广义的可以做质数的k次方的，然后用CRT（中国剩余定理）合并。
#include <cstdio> #define R register
typedef long long ll;
int pw0[], pw2[], pw5[];
int counter;
inline int qpow(R int base, R ll power, R int mod)
{
R int ret = ;
for (; power; power >>= , base = 1ll * base * base % mod)
power & ? ret = 1ll * ret * base % mod : ;
return ret;
}
int mod, k;
void exgcd(R int a, R int b, R int &x, R int &y)
{
if (!b) {x = , y = ; return ;}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(R int a, R int p)
{
R int x, y;
exgcd(a, p, x, y);
return (x % p + p) % p;
}
int f2[][], f5[][];
inline int fac(R ll n, R int fact, R int p, R int pk, R int *fk)
{
if (!n) return ;
R ll y = n / pk;
R int ret = 1ll * qpow(fact, y, pk) * fk[n % pk] % pk;
return 1ll * fac(n / p, fact, p, pk, fk) * ret % pk;
}
int ft2[], ft5[];
inline int Lucas(R ll n, R ll m, R int p, R int pk, R bool div)
{
R ll num = ;
for (R ll tmp = p; tmp <= n; tmp *= p) num += n / tmp;
for (R ll tmp = p; tmp <= m; tmp *= p) num -= m / tmp;
for (R ll tmp = p; tmp <= n - m; tmp *= p) num -= (n - m) / tmp; R int fact = p == ? ft2[k] : ft5[k],
*fk = p == ? f2[k] : f5[k],
fa = , fb, fc;
if (div)
{
if (p == ) --num;
else fa = inv(, pk);
}
if (num >= k) return ; fa = 1ll * fa * fac(n, fact, p, pk, fk) % pk;
fb = fac(m, fact, p, pk, fk);
fc = fac(n - m, fact, p, pk, fk);
fb = inv(fb, pk); fc = inv(fc, pk); return 1ll * fa * fb % pk * fc % pk * qpow(p, num, pk) % pk;
}
inline int C(R ll n, R ll m, R bool div = )
{
if (m > n) return ;
// printf("C(%lld, %lld) %d\n", n, m, div);
R int C2 = Lucas(n, m, , pw2[k], div);
R int C5 = Lucas(n, m, , pw5[k], div);
// printf("%d %d\n", C2, C5);
R int t2 = inv(pw5[k], pw2[k]);
R int t5 = inv(pw2[k], pw5[k]);
R int ans = (1ll * C2 * pw5[k] % mod * t2 + 1ll * C5 * pw2[k] % mod * t5) % mod;
// printf("%d\n", ans);
return ans;
}
int main()
{
R ll a, b;
pw0[] = pw2[] = pw5[] = ;
for (R int i = ; i < ; ++i)
pw0[i] = pw0[i - ] * ,
pw2[i] = pw2[i - ] * ,
pw5[i] = pw5[i - ] * ; for (R int i = ; i < ; ++i)
{
f2[i][] = ;
for (R int j = ; j < pw2[i]; ++j)
f2[i][j] = 1ll * f2[i][j - ] * (j % ? j : ) % pw2[i];
ft2[i] = f2[i][pw2[i] - ];
}
for (R int i = ; i < ; ++i)
{
f5[i][] = ;
for (R int j = ; j < pw5[i]; ++j)
f5[i][j] = 1ll * f5[i][j - ] * (j % ? j : ) % pw5[i];
ft5[i] = f5[i][pw5[i] - ];
} while (scanf("%lld%lld%d", &a, &b, &k) != EOF)
{
char str[];
R int ans = ;
mod = pw0[k];
ans = qpow(, a + b - , mod);
if (a == b) (ans += mod - C(a + a, a, )) %= mod;
else
{
if (((a + b) & ) == ) (ans += C(a + b, (a + b) / , )) %= mod;
for (R ll j = (a + b) / + ; j < a; ++j)
(ans += C(a + b, j)) %= mod;
}
sprintf(str, "%%0%dd\n", k);
printf(str, ans);
}
return ;
}
/*
488754688
1000000000000000 999999999990000 9
1000000000000000 999999999990000 8
1000000000000000 999999999990000 7
1000000000000000 999999999990000 6
1000000000000000 999999999990000 5
1000000000000000 999999999990000 4
1000000000000000 999999999990000 3
1000000000000000 999999999990000 2
1000000000000000 999999999990000 1
*/
D2T3
