题意

敌人有 $N$ 个工兵营地，第 $i$ 个工兵营地里开始时有 $a_i$个人
每行有一条命令，命令有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 表示结束，这条命令在每组数据最后出现;

做法

树状数组模板题，当然线段树也可以
属于单点更新，区间查询
区间查询即 query® - query(l-1) ，这里利用的是差分的思想

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(a,b)    ((a)>(b)?(b):(a))
#define max(a,b)    ((a)>(b)?(a):(b))
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;int tr[maxn], n;int lowbit(int x) {return x & (-x);
}void update(int id, int val) {for(int i = id; i <= n; i += lowbit(i))tr[i] += val;
}int query(int id) {int ans = 0;for(int i = id; i > 0; i -= lowbit(i))ans += tr[i];return ans;
}int main() {int T;scanf("%d", &T);for(int i = 1; i <= T; ++i) {printf("Case %d:\n", i);int x, y;scanf("%d", &n);for(int i = 0; i <= n; ++i) tr[i] = 0;for(int i = 1; i <= n; ++i) {scanf("%d", &x);update(i, x);}char s[10];while(~scanf("%s", s)) {if(s[0] == 'E') break;scanf("%d%d", &x, &y);if(s[0] == 'Q') printf("%d\n", query(y) - query(x - 1));else if(s[0] == 'A')update(x, y);else if(s[0] == 'S') update(x, -y);}}return 0;
}

目录

题意

每个星星有一个坐标 $(x_i,y_i)$，当有另一个星星的坐标 $(x_j,y_j)$，且 $x_j \leq x_i \&\& y_j \leq y_i$ 时，$i$ 星星的层次加 $1$
输入保证 $y$ 是升序的（也就是强行变一维）
最后询问层次 $0 \rightarrow (n-1)$ 的各有多少颗星星

做法

树状数组模板题，当然线段树也可以
属于单点更新，单点查询
单点查询即 $query(x)$，因为保证 $y$ 是升序，那么后面的星星对当前的星星都不会有贡献
统计当前星星的层次
然后单点更新 update(x, 1)
要注意的的一个地方是，本题是多组数据（很迷，我觉得题目看着是说单组数据的亚子啊 _(:з」∠)_ ）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(a,b)    ((a)>(b)?(b):(a))
#define max(a,b)    ((a)>(b)?(a):(b))
const int inf = 0x3f3f3f3f;
const int maxn = 5e4 + 5;int tr[maxn], n;
int res[maxn];int lowbit(int x) {return x & (-x);
}void update(int id, int val) {for(int i = id; i < maxn; i += lowbit(i))tr[i] += val;
}int query(int id) {int ans = 0;for(int i = id; i > 0; i -= lowbit(i))ans += tr[i];return ans;
}int main() {int x, y, ans = 0;while(~scanf("%d", &n)) {memset(tr, 0, sizeof(tr));memset(res, 0, sizeof(res));for(int i = 1; i <= n; ++i) {scanf("%d%d", &x, &y); res[query(++x)] += 1;update(x, 1);}for(int i = 0; i < n; ++i)printf("%d\n", res[i]);}return 0;
}

目录

未AC
究竟是道德的沦丧还是人性的扭曲
为何poj半夜无法登陆

题意

最初相邻村庄（编号从 $1 \rightarrow n$）之间有一条道路连接
接下来几条命令：
‘D x’: 摧毁编号为 $x$ 的村庄被摧毁，即相邻两个村庄到这个村庄的道路也没了
‘R’: 修复最后摧毁的那个村庄，即相邻两个村庄到这个村庄的道路也会修复
‘Q x’: 询问标号为 $x$ 的村庄最大连续可以互通的村庄长度

做法

看到这个下意识就想写线段树
线段树的话就是维护区间最大连续长度
然鹅，正在练习树状数组
最初可以初始化每个村庄的树状数组值为 $1$，一开始村庄都还在，$update(x, 1)$
那么摧毁也就只需要 $update(x, -1)$

主要在于询问部分
询问部分需要用到二分来查询，二分区间的边界，下面详细说明
$query(x)$ 可以得到 $1 \rightarrow x$ 间，所有还在的村庄的个数，也就是说，
如果询问一个区间内村庄的个数，那么当 $query(r) - query(l - 1) == r - l + 1$ 时，说明这一段区间内的村庄都存在
那么为了得到包含 $x$ 在内的连续村庄的个数，可以二分两次，
分别找到 $L \rightarrow id$ 最左边满足条件的 $L$, $id \rightarrow R$ 最右边满足条件的 $R$
最后 $R - L + 1$ 就是最终的答案

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(a,b)    ((a)>(b)?(b):(a))
#define max(a,b)    ((a)>(b)?(a):(b))
const int inf = 0x3f3f3f3f;
const int maxn = 5e4 + 5;bool vis[maxn];
int tr[maxn];
int st[maxn];
int n;int lowbit(int x) {return x & (-x);
}void update(int id, int val) {for(int i = id; i < maxn; i += lowbit(i))tr[i] += val;
}int query(int id) {int ans = 0;for(int i = id; i > 0; i -= lowbit(i))ans += tr[i];return ans;
}void solve(int id) {if(!vis[id]) {puts("0");return ;}int L, R; // 最有边界int l = 1, r = id, mid, x = query(id);while(l <= r) {mid = (l + r) >> 1;if(x - query(mid - 1) >= id - mid + 1)L = mid, r = mid - 1;else l = mid + 1;}l = id, r = n, x = query(id - 1);while(l <= r) {mid = (l + r) >> 1;if(query(mid) - x >= mid - id + 1)R = mid, l = mid + 1;elser = mid - 1;}printf("%d\n", R - L + 1);
}int main() {int m;scanf("%d%d", &n, &m);memset(tr, 0, sizeof(tr));memset(vis, true, sizeof(vis));for(int i = 1; i <= n; ++i) update(i, 1);char s[2]; int id, top = 0;while(m--) {scanf("%s", s);if(s[0] == 'R' && top) {id = st[top--], vis[id] = true;update(id, 1);}else{scanf("%d", &id);if(s[0] == 'D') {st[++top] = id, vis[id] = false;update(id, -1);}else{solve(id);}}} return 0;
}

目录

题意

做法

代码

目录

题意

做法

代码

目录

题意

做法

代码

目录

题意

做法

代码