1.敌兵布阵
题目描述
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地，Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚，每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手，但这些都逃不过C国的监视。
输入
第一行一个整数T，表示有T组数据。
每组数据第一行有一个正整数N（N<=50000），表示敌人有N个工兵营地，接下来一行有N个正整数，第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j，i和j为正整数，表示第i个营地增加j个人（j不超过30）；
(2) Sub i j，i和j为正整数，表示第i个营地减少j个人（j不超过30）；
(3) Query i j，i和j为正整数，i<=j，表示询问第i到第j个营地的总人数；
(4) End 表示结束，这条命令在每组数据最后出现。
输出
对第i组数据，首先输出“Case i:”和回车，
对于每个Query询问，输出一个整数并回车，表示询问的段中的总人数，这个数保持在int以内。
样例输入
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
样例输出
Case 1:
6
33
59
题解
#include <algorithm> #include <iostream> using namespace std; #define MID(l, r) (l + r) >> 1 #define lson root << 1 #define rson root << 1 | 1 const int maxn = 5e4 + 5; struct Tree { int l, r; int sum; } tree[maxn * 3]; int arr[maxn], ans; void Build(int root, int l, int r) { tree[root].l = l; tree[root].r = r; if (l == r) tree[root].sum = arr[l]; else { int mid = MID(l, r); Build(lson, l, mid); Build(rson, mid + 1, r); tree[root].sum = tree[lson].sum + tree[rson].sum; } } void Query(int root, int x, int y) { if (x <= tree[root].l && y >= tree[root].r) ans += tree[root].sum; else { int mid = MID(tree[root].l, tree[root].r); if (x > mid) { Query(rson, x, y); } else if (y <= mid) { Query(lson, x, y); } else { Query(lson, x, y); Query(rson, x, y); } } } void Update(int root, int x, int y) { tree[root].sum += y; if (tree[root].l == x && tree[root].r == x) return; int mid = MID(tree[root].l, tree[root].r); if (x > mid) Update(rson, x, y); else Update(lson, x, y); } int main() { int T; cin >> T; for (int flag = 1; flag <= T; flag++) { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; Build(1, 1, n); cout << "Case " << flag << ":" << endl; string ope; while (true) { cin >> ope; if (ope == "End") { break; } if (ope == "Add") { int x, y; cin >> x >> y; Update(1, x, y); continue; } if (ope == "Sub") { int x, y; cin >> x >> y; Update(1, x, -y); } if (ope == "Query") { int x, y; cin >> x >> y; ans = 0; Query(1, x, y); cout << ans << endl; } } } return 0; }
2. 最大数
题目描述
输入
输出
样例输入
5 100
A 96
Q 1
A 97
Q 1
Q 2
样例输出
96
93
96
题解
#include <iostream> #include <cstdio> #include <algorithm> #define MAX 100000 using namespace std; int mx[MAX * 4], a[MAX], m, d, x, n, now; void Build(int k, int l, int r, int x) { if (l == r && l == x) { mx[k] = a[l]; return; } int mid = (l + r) >> 1; if (x <= mid) { Build(k << 1, l, mid, x); } else { Build(k << 1 | 1, mid + 1, r, x); } mx[k] = max(mx[k << 1], mx[k << 1 | 1]); } int query(int k, int l, int r, int x, int y) { if (l == x && r == y) { return mx[k]; } int mid = (l + r) >> 1; if (y <= mid) { return query(k << 1, l, mid, x, y); } if (x > mid) { return query(k << 1 | 1, mid + 1, r, x, y); } return max(query(k << 1, l, mid, x, mid), query(k << 1 | 1, mid + 1, r, mid + 1, y)); } int main() { cin >> m >> d; for (int i = 1; i <= m; i++) { char op; cin >> op; if (op == 'A') { cin >> x; x += now; x %= d; a[++n] = x; Build(1, 1, m, n); } else { cin >> x; now = query(1, 1, m, n - x + 1, n); printf("%d\n", now); } } }
3.Distinct Characters Queries(英文题面)(线段树)
题目描述
输入
输出
样例输入
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
样例输出
3
1
2
题解
#include <iostream> #include <set> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 1; set<int> st[99]; char c[N]; int main() { cin >> (c + 1); int n; cin >> n; int len = strlen(c + 1); for (int i = 1; i <= len; ++i) { st[c[i] - 'a'].insert(i); } int f, t, d; char k; for (int i = 1; i <= n; ++i) { cin >> f; if (f == 1) { cin >> t >> k; st[c[t] - 'a'].erase(t); st[k - 'a'].insert(t); c[t] = k; } else { cin >> t >> d; int sum = 0; for (int j = 0; j < 26; ++j) { auto p = st[j].lower_bound(t); if (p != st[j].end() && *p <= d) sum++; } cout << sum << endl; } } }
4.Kth number
题目描述
Give you a sequence and ask you the kth big number of a inteval.
输入
The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
输出
For each test case, output m lines. Each line contains the kth big number.
样例输入
1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2
样例输出
2
题解
#include <iostream> #include <algorithm> #include <cstring> using namespace std; #define MAXN 100 struct treeNode { int val[MAXN]; int lStart, rEnd; int cnt; } segTree[4 * MAXN + 1]; int num[MAXN]; void build(int root, int arr[], int iStart, int iEnd) { if (iStart == iEnd) { segTree[root].cnt = 0; segTree[root].val[segTree[root].cnt++] = arr[iStart]; } else { int mid = (iStart + iEnd) >> 1; build(root * 2 + 1, arr, iStart, mid); build(root * 2 + 2, arr, mid + 1, iEnd); segTree[root].cnt = segTree[2 * root + 1].cnt + segTree[2 * root + 2].cnt; merge(segTree[2 * root + 1].val, segTree[2 * root + 1].val + segTree[2 * root + 1].cnt, segTree[2 * root + 2].val, segTree[2 * root + 2].val + segTree[2 * root + 2].cnt, segTree[root].val); } segTree[root].lStart = iStart; segTree[root].rEnd = iEnd; } int *query(int k, int l, int r, int &cnt) { int i; if (l <= segTree[k].lStart && segTree[k].rEnd <= r) { cnt = segTree[k].cnt; return segTree[k].val; } int *res = new int[MAXN]; int *resl, *resr; int cntr = 0, cntl = 0; int mid = (segTree[k].lStart + segTree[k].rEnd) >> 1; if (l <= mid) resl = query(k * 2 + 1, l, r, cntl); if (r > mid) resr = query(k * 2 + 2, l, r, cntr); merge(resl, resl + cntl, resr, resr + cntr, res); cnt = cntl + cntr; return res; } int main() { int m, n, cnt, r, l, i, k, t; cin >> t; while (t--) { cin >> n >> m; for (i = 0; i < n; i++) cin >> num[i]; build(0, num, 0, n - 1); while (m--) { cin >> l >> r >> k; int *res = query(0, l - 1, r - 1, cnt); cout << res[cnt - k] << endl; } } return 0; }
