区间的关系的计数 HDU 4638 离线+树状数组

时间:2023-12-17 15:39:32

题目大意:给你n个人,每个人都有一个id,有m个询问,每次询问一个区间[l,r],问该区间内部有多少的id是连续的(单独的也算是一个)

思路:做了那么多离线+树状数组的题目,感觉这种东西就是一个模板了,23333,反正都是定义右区间的。

这题的关键难度就是如何定义id是连续的呢。我们每次往区间里面放一个数值以后都要add(pos, 1),就是把pos~n的所有的关系都+1.然后如果说在pos之前就出现id-1,就要add(pos[id-1], -1)(同理id+1也是这样),这样子表示从pos[id-1]~n开始,后面的全都和他是存在组队的关系的,接下来就简单了。

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
const int maxn = 1e5 + ;
vector<pair<int, int> > q[maxn];
int pos[maxn], a[maxn], tree[maxn], ans[maxn];
int n, m;
inline int lowbit(int x){return x & -x;} void update(int x, int val){
for (int i = x; i <= n; i += lowbit(i)){
tree[i] += val;
}
} int sum(int x){
int ans = ;
for (int i = x; i > ; i -= lowbit(i)){
ans += tree[i];
}
return ans;
} int main(){
int t; cin >> t;
while (t--){
scanf("%d%d", &n, &m);
memset(pos, , sizeof(pos));
for (int i = ; i <= n; i++) {
scanf("%d", a + i);
pos[a[i]] = i;
q[i].clear();
}
for (int i = ; i <= m; i++){
int l, r; scanf("%d%d", &l, &r);
q[r].pb(mk(l, i));
}
memset(tree, , sizeof(tree));
for (int i = ; i <= n; i++){
update(i, );
if (a[i] + <= n && pos[a[i] + ] < i) update(pos[a[i] + ], -);
if (a[i] - >= && pos[a[i] - ] < i) update(pos[a[i] - ], -);
int len = q[i].size();
for (int j = ; j < len; j++){
pair<int, int> p = q[i][j];
ans[p.second] = sum(i) - sum(p.first - );
}
}
for (int i = ; i <= m; i++){
printf("%d\n", ans[i]);
}
}
return ;
}