#12：开学焦虑——4

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 int m;
 6 ll D, last;
 7 ll q[200005];
 8 int id[200005], tail, t;
 9 
10 inline void add(ll x) {
11     while (tail && q[tail] <= x)
12         tail--;
13     q[++tail] = x;
14     id[tail] = ++t;
15 }
16 
17 inline ll query(ll x) {
18     ll k = t - x + 1;
19     int pos = lower_bound(id+1, id+1+tail, k) - id;
20     return q[pos];
21 }
22 
23 int main() {
24     cin >> m >> D;
25     while (m--) {
26         char ch[3];
27         ll a;
28         scanf("%s%lld", ch, &a);
29         if (ch[0] == ‘A‘) {
30             add((a + last) % D);
31         } else {
32             printf("%lld\n", last = query(a));
33         }
34     }
35     return 0;
36 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxm = 200005;
 5 int M, D, last, n;
 6 struct Seg {
 7     int l, r, maxx;
 8 }t[maxm << 2];
 9 
10 void build(int l, int r, int p) {
11     t[p].l = l, t[p].r = r;
12     if (l == r) {
13         t[p].maxx = 0;
14         return;
15     }
16     int mid = (l + r) >> 1;
17     int ls = p << 1, rs = p << 1 | 1;
18     build(l, mid, ls);
19     build(mid+1, r, rs);
20     t[p].maxx = max(t[ls].maxx, t[rs].maxx);
21 }
22 
23 void Add(int l, int k, int p) {
24     if (t[p].l == t[p].r) {
25         t[p].maxx = k;
26         return;
27     }
28     int mid = (t[p].l + t[p].r) >> 1;
29     int ls = p << 1, rs = p << 1 | 1;
30     if (l <= mid)    Add(l, k, ls);
31     else    Add(l, k, rs);
32     t[p].maxx = max(t[ls].maxx, t[rs].maxx);
33 }
34 
35 int Query(int l, int r, int p) {
36     if (l <= t[p].l && t[p].r <= r) {
37         return t[p].maxx;
38     }
39     int mid = (t[p].l + t[p].r) >> 1;
40     int ls = p << 1, rs = p << 1 | 1;
41     int ret = 0;
42     if (l <= mid)    ret = max(ret, Query(l, r, ls));
43     if (mid < r)    ret = max(ret, Query(l, r, rs));
44     return ret;
45 }
46 
47 int main() {
48     scanf("%d%d", &M, &D);
49     build(1, M, 1);
50     while (M--) {
51         char ch[3];
52         int x;
53         scanf("%s%d", ch, &x);
54         if (ch[0] == ‘A‘) {
55             ++n;
56             Add(n, (x+last)%D, 1);
57         } else {
58             printf("%d\n", last = Query(n-x+1, n, 1));
59         }
60     }
61 }

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cctype>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <map>
 9 #define ri readint()
10 #define gc getchar()
11 #define rep(i, l, r) for (int i = l; i <= r; i++)
12 using namespace std;
13 
14 inline int readint() {
15     int x = 0, s = 1, c = gc;
16     while (c <= 32)    c = gc;
17     if (c == ‘-‘)    s = -1, c = gc;
18     for (; isdigit(c); c = gc)
19         x = x * 10 + c - 48;
20     return x * s;
21 }
22 
23 const int maxn = 4e4 + 5;
24 int n, m, T, last;
25 int a[maxn], val[maxn], id;
26 map<int, int> mp;
27 vector<int> v[maxn];
28 int block[maxn], f[205][205];
29 
30 void pre(int x) {
31     int cnt[maxn];
32     memset(cnt, 0, sizeof(cnt));
33     int maxx = 0, k = 0;
34     rep(i, (x - 1) * T + 1, n) {
35         int t = a[i];
36         cnt[t]++;
37         if (cnt[t] > maxx || (cnt[t] == maxx && val[t] < val[k])) {
38             maxx = cnt[k = t];
39         }
40         f[x][block[i]] = k;
41     }
42 }
43 
44 int Query(int ql, int qr, int k) {
45     return upper_bound(v[k].begin(), v[k].end(), qr) - lower_bound(v[k].begin(), v[k].end(), ql);
46 }
47 
48 int Query(int ql, int qr) {
49     int res = f[block[ql]+1][block[qr]-1];
50     int maxx = Query(ql, qr, res);
51     rep(i, ql, min(block[ql]*T, qr)) {
52         int t = Query(ql, qr, a[i]);
53         if (t > maxx || (t == maxx && val[a[i]] < val[res])) {
54             maxx = t;
55             res = a[i];
56         }
57     }
58     if (block[ql] != block[qr]) {
59         rep(i, (block[qr]-1) * T + 1, qr) {
60             int t = Query(ql, qr, a[i]);
61             if (t > maxx || (t == maxx && val[a[i]] < val[res])) {
62                 maxx = t;
63                 res = a[i];
64             }
65         }
66     }
67     return val[res];
68 }
69 
70 int main() {
71     n = ri, m = ri;
72     T = 300;
73 
74     rep(i, 1, n){
75         a[i] = ri;
76         if (!mp[a[i]]) {
77             val[++id] = a[i];
78             mp[a[i]] = id;
79         }
80         v[mp[a[i]]].push_back(i);
81         a[i] = mp[a[i]];
82     }
83     rep(i, 1, n)    block[i] = (i-1) / T + 1;
84     rep(i, 1, block[n])    pre(i);
85 
86     while (m--) {
87         int ql = ri, qr = ri;
88         ql = (ql + last - 1) % n + 1;
89         qr = (qr + last - 1) % n + 1;
90         if (ql > qr)    swap(ql, qr);
91         printf("%d\n", last = Query(ql, qr));
92     }
93     return 0;
94 }

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cctype>
  5 #include <iostream>
  6 #include <algorithm>
  7 #define ll long long
  8 #define ri readint()
  9 #define gc getchar()
 10 #define rep(i, l, r) for (int i = l; i <= r; i++)
 11 using namespace std;
 12 
 13 const int N = 25 * 1e4 + 5;
 14 struct Stone {
 15     ll x, y, m, p, r, d;
 16 }q[N], st[N];
 17 int L[N], R[N], M[N];
 18 int n, T, block;
 19 bool mark[N];
 20 
 21 inline int readint() {
 22     int x = 0, s = 1, c = gc;
 23     while (c <= 32)    c = gc;
 24     if (c == ‘-‘)    s = -1, c = gc;
 25     for (; isdigit(c); c = gc)
 26         x = x * 10 + c - 48;
 27     return x * s;
 28 }
 29 
 30 inline ll sqr(ll x) {
 31     return x * x;
 32 }
 33 
 34 inline bool cmp1(const Stone &a, const Stone &b) {
 35     return a.m < b.m;
 36 }
 37 
 38 inline bool cmp2(const Stone &a, const Stone &b) {
 39     return a.d < b.d;
 40 }
 41 
 42 void READ() {
 43     q[0].x = ri, q[0].y = ri, q[0].p = ri, q[0].r = ri;
 44     n = ri;
 45     T = sqrt(n);
 46     rep(i, 1, n) {
 47         st[i].x = ri;
 48         st[i].y = ri;
 49         st[i].m = ri;
 50         st[i].p = ri;
 51         st[i].r = ri;
 52         st[i].d = sqr(st[i].x - q[0].x) + sqr(st[i].y - q[0].y);
 53     }
 54 }
 55 
 56 void BLOCK() {
 57     sort(st+1, st+1+n, cmp1);
 58     block = (n - 1) / T + 1;
 59     rep(i, 1, block) {
 60         L[i] = (i - 1) * T + 1;
 61         R[i] = min(i * T, n);
 62         M[i] = st[R[i]].m;
 63         sort(st+L[i], st+R[i]+1, cmp2);
 64     }
 65 }
 66 
 67 int BFS() {
 68     int l = 0, r = 1;
 69     while (l < r) {
 70         int k = 0;
 71         rep(i, 1, block) {
 72             if (M[i] > q[l].p)
 73                 break;
 74             k = i;
 75         }
 76 
 77         rep(i, 1, k) {
 78             while (L[i] <= R[i] && st[L[i]].d <= sqr(q[l].r)) {
 79                 if (!mark[L[i]]) {
 80                     mark[L[i]] = true;
 81                     q[r++] = st[L[i]];
 82                 }
 83                 ++L[i];
 84             }
 85         }
 86         if (block != k++) {
 87             rep(i, L[k], R[k]) {
 88                 if (!mark[i] && st[i].m <= q[l].p && st[i].d <= sqr(q[l].r)) {
 89                     mark[i] = true;
 90                     q[r++] = st[i];
 91                 }
 92             }
 93         }
 94 
 95         ++l;
 96     }
 97     return r - 1;
 98 }
 99 
100 int main() {
101     READ();
102     BLOCK();
103     cout << BFS() << endl;
104     return 0;
105 }

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 const int N = 1e5 + 5;
 6 int n, m, col[N];
 7 int T, block[N];
 8 ll ans, sum[N];
 9 struct Mo {
10     int l, r, id;
11     ll A, B;
12 }q[N];
13 
14 bool cmp1(Mo a, Mo b) {
15     return block[a.l] == block[b.l] ? a.r < b.r : a.l < b.l;
16 }
17 
18 bool cmp2(Mo a, Mo b) {
19     return a.id < b.id;
20 }
21 
22 ll sqr(ll x) {
23     return x * x;
24 }
25 
26 void change(int x, int add) {
27     ans -= sqr(sum[col[x]]);
28     sum[col[x]] += add;
29     ans += sqr(sum[col[x]]);
30 }
31 
32 int main() {
33     cin >> n >> m;
34     T = sqrt(n);
35     for (int i = 1; i <= n; i++) {
36         scanf("%d", &col[i]);
37         block[i] = (i - 1) / T + 1;
38     }
39     for (int i = 1; i <= m; i++) {
40         scanf("%d%d", &q[i].l, &q[i].r);
41         q[i].id = i;
42     }
43     sort(q+1, q+1+m, cmp1);
44 
45     int l = 1, r = 0;
46     for (int i = 1; i <= m; i++) {
47         while (l < q[i].l)    change(l++, -1);
48         while (l > q[i].l)    change(--l, 1);
49         while (r < q[i].r)    change(++r, 1);
50         while (r > q[i].r)    change(r--, -1);
51 
52         if (q[i].l == q[i].r) {
53             q[i].A = 0ll;
54             q[i].B = 1ll;
55             continue;
56         }
57         ll t = q[i].r - q[i].l + 1;
58         q[i].A = ans - t;
59         q[i].B = sqr(t) - t;
60         ll gcd = __gcd(q[i].A, q[i].B);
61         if (!gcd)    q[i].B = 1ll;
62         else    q[i].A /= gcd, q[i].B /= gcd;
63     }
64 
65     sort(q+1, q+1+m, cmp2);
66     for (int i = 1; i <= m; i++)
67         printf("%lld/%lld\n", q[i].A, q[i].B);
68 
69     return 0;
70 }