1 #include <cstdio>  2 #include <cmath>  3 #include <set>  4 #include <algorithm>  5   6 #define R register  7 #define P std::pair<int, int>  8 #define mkp std::make_pair  9 #define maxn 100010 10 #define fir first 11 #define sec second 12 int v[maxn], ch[maxn][2], fa[maxn], tot; 13 std::set<P> s; 14 int q[maxn]; 15 int dfn[maxn], inv[maxn], timer, pos[maxn], ltag; 16 int ql, qr; 17 int hash[maxn]; 18 int bt[maxn]; 19 void add(R int x, R int val) {for (; x <= tot; x += x & -x) bt[x] += val;} 20 int query(R int x) {R int ret = 0; for (; x; x -= x & -x) ret += bt[x]; return ret;} 21 void modify(R int l, R int r, R int v) 22 { 23 //    printf("l = %d r = %d v = %d\n", l, r, v); 24     add(l, v); add(r + 1, -v); 25 } 26 int main() 27 { 28     R int n, root; scanf("%d", &n); 29     s.insert(mkp(0, 0)); 30     s.insert(mkp(1e9 + 7, 0)); 31     for (R int i = 1; i <= n; ++i) 32     { 33         R int opt; scanf("%d", &opt); q[i] = opt; 34         if (opt == 1) {R int key; scanf("%d", &key); v[++tot] = key; hash[tot] = key;} 35     } 36     std::sort(hash + 1, hash + tot + 1); 37     for (R int i = 1; i <= n; ++i) dfn[i] = std::lower_bound(hash + 1, hash + tot + 1, v[i]) - hash; 38     for (R int i = 1, nw = 0; i <= n; ++i) 39     { 40         R int opt = q[i]; 41         if (opt == 1) 42         { 43             R P now = mkp(v[++nw], nw); 44             R P prev = *(--s.upper_bound(now)), next = *s.upper_bound(now); 45             s.insert(now); 46             if (prev.sec && !ch[prev.sec][1]) 47             { 48                 ch[prev.sec][1] = nw; 49                 fa[nw] = prev.sec; 50             } 51             else if (next.sec && !ch[next.sec][0]) 52             { 53                 ch[next.sec][0] = nw; 54                 fa[nw] = next.sec; 55             } 56             !fa[nw] ? root = nw : 0; 57  58             R int dep; 59             printf("%d\n", dep = fa[nw] ? query(dfn[fa[nw]]) + 1 : 1); 60             modify(dfn[nw], dfn[nw], dep - query(dfn[nw])); 61         } 62         else if (opt == 2) 63         { 64             R P xmin = *(++s.begin()); R int xc = xmin.sec; 65             printf("%d\n", query(dfn[xc])); 66 //            printf("fa %d\n", fa[xc]); 67             modify(!fa[xc] ? tot + 1 : dfn[fa[xc]], tot, 1); 68             modify(dfn[xc], dfn[xc], 1 - query(dfn[xc])); 69  70             if (root != xc) 71             { 72                 ch[fa[xc]][0] = ch[xc][1]; 73                 fa[ch[xc][1]] = fa[xc]; 74                 fa[root] = xc; 75                 ch[xc][1] = root; 76                 root = xc; 77                 fa[xc] = 0; 78             } 79         } 80         else if (opt == 3) 81         { 82             R P xmax = *(++s.rbegin()); R int xc = xmax.sec; 83             printf("%d\n", query(dfn[xc])); 84             modify(1, !fa[xc] ? 0 : dfn[fa[xc]], 1); 85             modify(dfn[xc], dfn[xc], 1 - query(dfn[xc])); 86  87             if (root != xc) 88             { 89                 ch[fa[xc]][1] = ch[xc][0]; 90                 fa[ch[xc][0]] = fa[xc]; 91                 fa[root] = xc; 92                 ch[xc][0] = root; 93                 root = xc; 94                 fa[xc] = 0; 95             } 96         } 97         else if (opt == 4) 98         { 99             R P xmin = *(++s.begin()); R int xc = xmin.sec;100             printf("%d\n", query(dfn[xc]));101             modify(dfn[xc] + 1 , !fa[xc] ? tot : dfn[fa[xc]] - 1, -1);102             103             xc == root ? fa[root = ch[xc][1]] = 0 :104             (ch[fa[xc]][0] = ch[xc][1],105             fa[ch[xc][1]] = fa[xc]);106             s.erase(xmin);107         }108         else109         {110             R P xmax = *(++s.rbegin()); R int xc = xmax.sec;111 //            printf("max %d %d\n", xc, fa[xc]);112             printf("%d\n", query(dfn[xc]));113             modify(!fa[xc] ? 1 : dfn[fa[xc]] + 1, dfn[xc] - 1, -1);114 115             xc == root ? fa[root = ch[xc][0]] = 0 :116             (ch[fa[xc]][1] = ch[xc][0],117             fa[ch[xc][0]] = fa[xc]);118             s.erase(xmax);119         }120     }121     return 0;122 }123 /*124 6125 1 1126 1 2127 1 4128 4129 2130 5131 性质：二叉查找树的子树的权值对应的是一个区间。并且有且仅有所有子树内的点在这个区间内。132 */

  1 #include <cstdio>  2 #include <algorithm>  3 #include <cstring>  4   5 #define R register  6 #define maxn 200010  7 #define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))  8 inline int F()  9 { 10     R char ch; R int cnt; 11     while (ch = getchar(), ch < ‘0‘ || ch > ‘9‘) ; 12     cnt = ch - ‘0‘; 13     while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘) cnt = cnt * 10 + ch - ‘0‘; 14     return cnt; 15 } 16 typedef long long ll; 17 struct Query { 18     int l, r; 19 } q[maxn]; 20 struct Chain { 21     Chain *next; 22     int id; 23 } *last[maxn], mem[maxn], *tot = mem; 24 struct Opt { 25     int x, id, type; 26     inline bool operator < (const Opt &that) const {return x < that.x;} 27 } op[maxn << 1]; 28 int ans1[maxn]; ll ans2[maxn]; 29 int st[maxn], top, a[maxn]; 30 int ql, qr; 31 ll tr[maxn << 2], tag[maxn << 2]; 32 inline void pushdown(R int o, R int l, R int r, R int mid) 33 { 34     if (tag[o]) 35     { 36         tag[o << 1] += tag[o]; 37         tag[o << 1 | 1] += tag[o]; 38         tr[o << 1] += 1ll * tag[o] * (mid - l + 1); 39         tr[o << 1 | 1] += 1ll * tag[o] * (r - mid); 40         tag[o] = 0; 41     } 42 } 43 inline void update(R int o) {tr[o] = tr[o << 1] + tr[o << 1 | 1];} 44 void modify(R int o, R int l, R int r) 45 { 46     if (ql <= l && r <= qr) 47     { 48         ++tag[o]; tr[o] += (r - l + 1); 49         return ; 50     } 51     R int mid = l + r >> 1; 52     pushdown(o, l, r, mid); 53     if (ql <= mid) modify(o << 1, l, mid); 54     if (mid < qr) modify(o << 1 | 1, mid + 1, r); 55     update(o); 56 } 57 ll query(R int o, R int l, R int r) 58 { 59     if (ql <= l && r <= qr) return tr[o]; 60     R int mid = l + r >> 1; 61     R ll ret = 0; 62     pushdown(o, l, r, mid); 63     if (ql <= mid) ret += query(o << 1, l, mid); 64     if (mid < qr) ret += query(o << 1 | 1, mid + 1, r); 65     return ret; 66 } 67 int bt[maxn], n, lef[maxn], rig[maxn], r[maxn], Fa[maxn]; 68 int Find(R int x) {return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);} 69 inline void add(R int x) {for (; x <= n; x += x & -x) ++bt[x];} 70 inline int query(R int x) {R int ret = 0; for (; x; x -= x & -x) ret += bt[x]; return ret;} 71 int main() 72 { 73     n = F(); R int m = F(), p1 = F(), p2 = F(); 74     for (R int i = 1; i <= n; ++i) a[i] = F(), r[a[i]] = i, Fa[i] = lef[i] = rig[i] = i; 75     R int opcnt = 0; 76     for (R int i = 1; i <= m; ++i) 77     { 78         q[i] = (Query) {F(), F()}; 79         *++tot = (Chain) {last[q[i].r], i}; last[q[i].r] = tot; 80         op[++opcnt] = (Opt) {q[i].l - 1, i, -1}; 81         op[++opcnt] = (Opt) {q[i].r, i, 1}; 82     } 83  84     memset(bt, 0, (n + 1) << 2); top = 0; 85     for (R int i = 1; i <= n; ++i) 86     { 87         R int rr = i - 2; 88         while (top && a[st[top]] < a[i]) add(st[top--]); 89         if (top) add(st[top]); 90         st[++top] = i; 91         for (R Chain *iter = last[i]; iter; iter = iter -> next) 92             ans1[iter -> id] += query(q[iter -> id].r) - query(q[iter -> id].l - 1); 93     } 94  95     std::sort(op + 1, op + opcnt + 1); 96     for (R int i = 1; i <= n; ++i) 97     { 98         R int ps = r[i], f1; 99         if (ps != 1 && a[ps - 1] < i) lef[ps] = lef[f1 = Find(ps - 1)], Fa[f1] = ps;100         if (ps != n && a[ps + 1] < i) rig[ps] = rig[f1 = Find(ps + 1)], Fa[f1] = ps;101     }102     R int p = 1;103     while (op[p].x == 0) ++p;104     for (R int i = 1; i <= n; ++i)105     {106 //        printf("%d %d\n", lef[i], rig[i]);107         ql = lef[i]; qr = rig[i];108         modify(1, 1, n);109         while (op[p].x == i)110         {111             ql = q[op[p].id].l; qr = q[op[p].id].r;112             ans2[op[p].id] += op[p].type * query(1, 1, n);113             ++p;114         }115     }116     for (R int i = 1; i <= m; ++i) printf("%lld\n", 1ll * ans1[i] * p1 + (ans2[i] - (q[i].r - q[i].l + 1) - ans1[i]) * p2);117     return 0;118 }119 /*120 9 4121 12 5122 2 0123 5 1124 5 2125 30126 39127 4128 13129 16130 131 */

 1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4  5 #define R register 6 #define maxn 262145 7 #define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0) 8 typedef double db; 9 const db pi = acos(-1);10 struct Complex {11     db x, y;12     inline Complex operator - (const Complex &that) const {return (Complex) {x - that.x, y - that.y};}13     inline Complex operator * (const Complex &that) const {return (Complex) {x * that.x - y * that.y, x * that.y + that.x * y};}14     inline void operator += (const Complex &that) {x += that.x; y += that.y;}15 } w[maxn << 1];16 int N;17 void init()18 {19     R int h = N >> 1;20     for (R int i = 0; i < N; ++i) w[i + h] = (Complex) {cos(2 * pi / N * i), sin(2 * pi / N * i)};21     for (R int i = h; i--; ) w[i] = w[i << 1];22 }23 void bit_reverse(R Complex *a, R Complex *b)24 {25     for (R int i = 0; i < N; ++i) b[i] = a[i];26     for (R int i = 0, j = 0; i < N; ++i)27     {28         i > j ? std::swap(b[i], b[j]), 1 : 0;29         for (R int l = N >> 1; (j ^= l) < l; l >>= 1) ;30     }31 }32 void dft(R Complex *a)33 {34     for (R int l = 2, m = 1; m < N; l <<= 1, m <<= 1)35         for (R int i = 0; i < N; i += l)36             for (R int j = 0; j < m; ++j)37             {38                 R Complex tmp = a[i + j + m] * w[j + m];39                 a[i + j + m] = a[i + j] - tmp;40                 a[i + j] += tmp;41             }42 }43 Complex a[maxn], b[maxn], c[maxn], ta[maxn], tb[maxn], tc[maxn];44 int main()45 {46     R int n, m, ans = 0x7fffffff, ret = 0, sum = 0; scanf("%d%d", &n, &m);47     for (R int i = 0; i < n; ++i) scanf("%lf", &a[i].x), sum -= a[i].x;48     for (R int i = 0; i < n; ++i) scanf("%lf", &b[i].x), sum += b[i].x;49     std::reverse(b, b + n);50     for (R int i = 0; i < n; ++i) b[i + n] = b[i];51     for (N = 1; N < (n << 1); N <<= 1);52     init();53     R int ccc = round((db) sum / n);54 55     for (R int i = 0; i < n; ++i) a[i].x += ccc, ret += a[i].x * a[i].x + b[i].x * b[i].x;56 //    printf("%d %d\n", ccc, ret);57     bit_reverse(a, ta);58     bit_reverse(b, tb);59     dft(ta); dft(tb);60     for (R int i = 0; i < N; ++i) c[i] = ta[i] * tb[i];61     std::reverse(c + 1, c + N);62     bit_reverse(c, tc); dft(tc);63 //    for (R int i = 0; i < N; ++i) printf("%lf %lf\n", tc[i].x, tc[i].y);64     for (R int i = 0; i < n; ++i) cmin(ans, (int) ret - (2 * tc[i + n].x / N));65 66     printf("%d\n", ans);67     return 0;68 }

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <map>  5 #include <bitset>  6   7 #define R register  8 #define maxn 110  9 int a[maxn], w[maxn]; 10 int f[maxn][maxn]; 11 const int oo = 1e8; 12 #define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0) 13 #define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b)) 14 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b)) 15 const int mod = 8260817; 16 typedef long long ll; 17 struct Queue { 18     int step, level, f; 19 } q[10000010]; 20 struct Hash { 21     Hash *next; 22     ll key; 23 } *last[mod], mem[mod], *tot = mem; 24 inline ll hash_key(R int a, R int b) 25 { 26     return 1ll * b * 233 + a; 27 } 28 inline bool insert(R int a, R int b) 29 { 30     R ll key = hash_key(a, b); 31     R int pos = key % mod; 32     for (R Hash *iter = last[pos]; iter; iter = iter -> next) 33         if (iter -> key == key) return 0; 34     *++tot = (Hash) {last[pos], key}; last[pos] = tot; 35     return 1; 36 } 37 struct Data { 38     int f, s; 39     inline bool operator < (const Data &that) const {return f < that.f;} 40 } st[maxn * maxn * maxn]; 41 int scnt, qu[30]; 42 int main() 43 { 44     R int n, m, mc; scanf("%d%d%d", &n, &m, &mc); 45     for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]); 46     for (R int i = 1; i <= n; ++i) scanf("%d", &w[i]); 47     memset(f, -63, sizeof (f)); 48     f[0][mc] = 0; 49     for (R int i = 1; i <= n; ++i) 50     { 51         for (R int j = a[i]; j <= mc; ++j) 52             cmax(f[i][j - a[i]], f[i - 1][j] + 1), 53             cmax(f[i][dmin(j - a[i] + w[i], mc)], f[i - 1][j]); 54     } 55     R int Day = -1; 56     for (R int j = 0; j <= n; ++j) for (R int i = 0; i <= mc; ++i) cmax(Day, f[j][i]); 57     R int oo = 0; 58     for (R int i = 1; i <= m; ++i) scanf("%d", &qu[i]), cmax(oo, qu[i]); 59  60     R int head = 0, tail = 1; 61     q[1] = (Queue) {0, 0, 1}; 62     while (head < tail) 63     { 64         R Queue now = q[++head]; 65         if (insert(0, now.f)) st[++scnt] = (Data) {now.f, now.step + 1}; 66         if (now.step >= Day - 1) continue; 67         if (now.level > 0 && oo / now.level < now.f) continue; 68         if (insert(now.level + 1, now.f)) q[++tail] = (Queue) {now.step + 1, now.level + 1, now.f}; 69  70         if (1ll * now.f * now.level <= oo && now.f > 0) 71         { 72             if (insert(now.level, now.f * now.level)) 73                 q[++tail] = (Queue) {now.step + 1, now.level, now.f * now.level}; 74         } 75     } 76     st[++scnt] = (Data) {0, 0}; 77     std::sort(st + 1, st + scnt + 1); 78     for (R int _ = 1; _ <= m; ++_) 79     { 80         R int c = qu[_], flag = 0; 81         if (Day <= 0) {puts("0"); continue;} 82         if (c <= Day) {puts("1"); continue;} 83         R int j = 0, mx = -oo * 2; 84         for (R int i = scnt; i; --i) 85         { 86             for (; j < scnt && st[j + 1].f + st[i].f <= c; ++j, cmax(mx, st[j].f - st[j].s)); 87             if (mx + st[i].f - st[i].s >= c - Day) 88             { 89                 flag = 1; 90                 break; 91             } 92         } 93         printf("%d\n", flag); 94     } 95     return 0; 96 } 97 /* 98 10 20 100 99 22 18 15 16 20 19 33 15 38 49100 92 14 94 92 66 94 1 16 90 51101 4102 5103 9104 338105 5222106 549107 7491108 9109 12110 3288111 3112 1113 2191114 833115 3116 6991117 2754118 3231119 360120 6121 122 1123 1124 1125 0126 0127 0128 0129 1130 1131 0132 1133 1134 0135 0136 1137 0138 0139 0140 0141 1142 */

  1 #include <cstdio>  2   3 #define R register  4 typedef long long ll;  5 int pw0[10], pw2[10], pw5[10];  6 int counter;  7 inline int qpow(R int base, R ll power, R int mod)  8 {  9     R int ret = 1; 10     for (; power; power >>= 1, base = 1ll * base * base % mod) 11         power & 1 ? ret = 1ll * ret * base % mod : 0; 12     return ret; 13 } 14 int mod, k; 15 void exgcd(R int a, R int b, R int &x, R int &y) 16 { 17     if (!b) {x = 1, y = 0; return ;} 18     exgcd(b, a % b, y, x); 19     y -= a / b * x; 20 } 21 inline int inv(R int a, R int p) 22 { 23     R int x, y; 24     exgcd(a, p, x, y); 25     return (x % p + p) % p; 26 } 27 int f2[10][1024], f5[10][1953125]; 28 inline int fac(R ll n, R int fact, R int p, R int pk, R int *fk) 29 { 30     if (!n) return 1; 31     R ll y = n / pk; 32     R int ret = 1ll * qpow(fact, y, pk) * fk[n % pk] % pk; 33     return 1ll * fac(n / p, fact, p, pk, fk) * ret % pk; 34 } 35 int ft2[10], ft5[10]; 36 inline int Lucas(R ll n, R ll m, R int p, R int pk, R bool div) 37 { 38     R ll num = 0; 39     for (R ll tmp = p; tmp <= n; tmp *= p) num += n / tmp; 40     for (R ll tmp = p; tmp <= m; tmp *= p) num -= m / tmp; 41     for (R ll tmp = p; tmp <= n - m; tmp *= p) num -= (n - m) / tmp; 42      43     R int fact = p == 2 ? ft2[k] : ft5[k], 44           *fk  = p == 2 ? f2[k]  : f5[k], 45           fa = 1, fb, fc; 46     if (div) 47     { 48         if (p == 2) --num; 49         else fa = inv(2, pk); 50     } 51     if (num >= k) return 0; 52  53     fa = 1ll * fa * fac(n, fact, p, pk, fk) % pk; 54     fb = fac(m, fact, p, pk, fk); 55     fc = fac(n - m, fact, p, pk, fk); 56     fb = inv(fb, pk); fc = inv(fc, pk); 57      58  59     return 1ll * fa * fb % pk * fc % pk * qpow(p, num, pk) % pk; 60 } 61 inline int C(R ll n, R ll m, R bool div = 0) 62 { 63     if (m > n) return 0; 64 //    printf("C(%lld, %lld) %d\n", n, m, div); 65     R int C2 = Lucas(n, m, 2, pw2[k], div); 66     R int C5 = Lucas(n, m, 5, pw5[k], div); 67 //    printf("%d %d\n", C2, C5); 68     R int t2 = inv(pw5[k], pw2[k]); 69     R int t5 = inv(pw2[k], pw5[k]); 70     R int ans = (1ll * C2 * pw5[k] % mod * t2 + 1ll * C5 * pw2[k] % mod * t5) % mod; 71 //    printf("%d\n", ans); 72     return ans; 73 } 74 int main() 75 { 76     R ll a, b; 77     pw0[0] = pw2[0] = pw5[0] = 1; 78     for (R int i = 1; i < 10; ++i) 79         pw0[i] = pw0[i - 1] * 10, 80         pw2[i] = pw2[i - 1] * 2, 81         pw5[i] = pw5[i - 1] * 5; 82  83     for (R int i = 1; i < 10; ++i) 84     { 85         f2[i][0] = 1; 86         for (R int j = 1; j < pw2[i]; ++j) 87             f2[i][j] = 1ll * f2[i][j - 1] * (j % 2 ? j : 1) % pw2[i]; 88         ft2[i] = f2[i][pw2[i] - 1]; 89     } 90     for (R int i = 1; i < 10; ++i) 91     { 92         f5[i][0] = 1; 93         for (R int j = 1; j < pw5[i]; ++j) 94             f5[i][j] = 1ll * f5[i][j - 1] * (j % 5 ? j : 1) % pw5[i]; 95         ft5[i] = f5[i][pw5[i] - 1]; 96     } 97  98     while (scanf("%lld%lld%d", &a, &b, &k) != EOF) 99     {100         char str[10];101         R int ans = 0;102         mod = pw0[k];103         ans = qpow(2, a + b - 1, mod);104         if (a == b) (ans += mod - C(a + a, a, 1)) %= mod;105         else106         {107             if (((a + b) & 1) == 0) (ans += C(a + b, (a + b) / 2, 1)) %= mod;108             for (R ll j = (a + b) / 2 + 1; j < a; ++j)109                 (ans += C(a + b, j)) %= mod;110         }111         sprintf(str, "%%0%dd\n", k);112         printf(str, ans);113     }114     return 0;115 }116 /*117 488754688118 1000000000000000 999999999990000 9119 1000000000000000 999999999990000 8120 1000000000000000 999999999990000 7121 1000000000000000 999999999990000 6122 1000000000000000 999999999990000 5123 1000000000000000 999999999990000 4124 1000000000000000 999999999990000 3125 1000000000000000 999999999990000 2126 1000000000000000 999999999990000 1127 */