题目链接
题目大意
n个数的序列，m次询问。 求一段区间连续数字的段数 。 (1 3 5 4 2) 询问[2,4]区间则3,5,4为连续序列输出 1 。
解题思路
我觉得这是一道不错的题目。 定义线段是求的连续序列。 首先将所有的询问离线，按照Li递增排序。 我们可以用一个结构维护Li为起点加入所有点后的各区间线段数，对于每个以Li为起点的询问进行处理。 当然这样不够，我们还要消除Li之前加入的点的影响。 所以我们可以用树状数组或者线段树维护区间的线段数。
利用树状数组维护：树状数组在对于线段的操作没有线段树强大，但是我们可以对于问题进行转化，维护加入某点之后线段数的增减数量，有点类似于扫描线，对与加入新的点x，我们可以看看x-1，x+1是否已经存在。如果都存在就update（pos[x]，-1）,因为x合并了两条线段。同理存在其中一个update（pos[x]，0）,否则单独自己成为一条线段就update（pos[x]，1）。对于消除x的影响时，只需update（pos[x-1]，1），update（pos[x+1]，1）。因为如果x对于x+1，或x-1有影响那么说明x+1，x-1一定在x之后加入，，去掉x之后它们要+1。 线段树维护的话就直接维护线段数就好了。
;LL;const int INF = 0x7fffffff;const int MOD = 1e9 + 7;const int N = 1e5 + 10;bool vis[N];int id[N], c[N], ans[N], pos[N];struct Interval {int l, r, i;} Q[N];int cmp(Interval a, Interval b) {return a.l < b.l;}int lowbit(int x) {return x & -x;}int update(int i, int v) {for( ; i < N; i += lowbit(i)) {c[i] += v;}}int query(int i) {int res = 0;for(; i; i -= lowbit(i)) {res += c[i];}return res;}int getsum (int l, int r) {return query(r) – query(l – 1);}int main() {#ifdef Tally_Hofreopen(“in.txt”, “r”, stdin);#endif // Tally_Hoint T, n, m;scanf(“%d”, &T);while(T–) {scanf(“%d%d”, &n, &m);memset(c, 0, sizeof(c));memset(vis, 0, sizeof(vis));for(int i = 1; i <= n; i++) {scanf(“%d”, &id[i]);pos[id[i]] = i;}for(int i = 0; i < m; i++) {int l, r;scanf(“%d%d”, &Q[i].l, &Q[i].r);Q[i].i = i;}sort(Q, Q + m, cmp);for(int i = 1; i <= n; i++) {vis[id[i]] = 1;if(vis[id[i] – 1] && vis[id[i] + 1]) {update(i, -1);} else if(vis[id[i] – 1] || vis[id[i] + 1]) {update(i, 0);} else {update(i, 1);}}int cur = 1;for(int i = 0; i < m; i++) {int L = Q[i].l, R = Q[i].r;while(cur < L) {if(id[cur] != 1) update(pos[id[cur] – 1], 1);if(id[cur] != n) update(pos[id[cur] + 1], 1);cur++;}ans[Q[i].i] = getsum(L, R);}for(int i = 0; i < m; i++) {printf(“%d\n”, ans[i]);}}return 0;}
不义而富且贵，于我如浮云。
