hdu 4638 Group(離線線段樹)

搞了這麼久，終於做了一個離線線段樹。。。。個人覺得，如果詢問間會相互影響到的話，就用所謂“離線”來搞。。。

這個題，考慮從左到右一個一個地加數，加到a[i]時，如果a[i]-1或a[i]+1有一個加過，總段數不變，都加過，合並兩端，段數減一；如果都沒加過，加入a[i]相當於新加了一段。

將所有詢問按右端點從小到大處理（一個大的區間，增加的元素會對小的區間造成影響）；邊處理邊加數。

include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdlib>  
#include<fstream>  
#include<sstream>  
#include<bitset>  
#include<vector>  
#include<string>  
#include<cstdio>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<stack>  
#include<map>  
#include<set>  
#define FF(i, a, b) for(int i=a; i<b; i++)  
#define FD(i, a, b) for(int i=a; i>=b; i--)  
#define REP(i, n) for(int i=0; i<n; i++)  
#define CLR(a, b) memset(a, b, sizeof(a))  
#define debug puts("**debug**")  
#define LL long long  
#define PB push_back  
using namespace std; 
 
const int maxn = 100001; 
int a[maxn], c[maxn], pos[maxn], ans[maxn]; 
int n, m; 
struct Q 
{ 
    int l, r, id; 
    bool operator < (const Q rhs) const 
    { 
        return r < rhs.r; 
    } 
}q[maxn]; 
 
int low(int x) {return x & (-x);} 
void add(int x, int v) 
{ 
    while(x <= n) 
    { 
        c[x] += v; 
        x += low(x); 
    } 
} 
int getsum(int x) 
{ 
    int ret = 0; 
    while(x > 0) 
    { 
        ret += c[x]; 
        x -= low(x); 
    } 
    return ret; 
} 
 
int main() 
{ 
    int T; scanf("%d", &T); 
    while(T--) 
    { 
        scanf("%d%d", &n, &m); 
        FF(i, 1, n+1) scanf("%d", &a[i]), pos[a[i]] = i, c[i] = 0; 
        REP(i, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i; 
        sort(q, q+m); 
        int j = 1; 
        for(int i=0; i<m; ) 
        { 
            if(q[i].r < j) 
            { 
                ans[q[i].id] = getsum(q[i].r) - getsum(q[i].l-1); 
                i++; 
            } 
            else 
            { 
                add(j, 1); 
                if(a[j] > 1 && pos[a[j]-1] < j) add(pos[a[j]-1], -1); 
                if(a[j] < n && pos[a[j]+1] < j) add(pos[a[j]+1], -1); 
                j++; 
            } 
        } 
        REP(i, m) printf("%d\n", ans[i]); 
    } 
    return 0; 
} 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
using namespace std;

const int maxn = 100001;
int a[maxn], c[maxn], pos[maxn], ans[maxn];
int n, m;
struct Q
{
    int l, r, id;
    bool operator < (const Q rhs) const
    {
        return r < rhs.r;
    }
}q[maxn];

int low(int x) {return x & (-x);}
void add(int x, int v)
{
    while(x <= n)
    {
        c[x] += v;
        x += low(x);
    }
}
int getsum(int x)
{
    int ret = 0;
    while(x > 0)
    {
        ret += c[x];
        x -= low(x);
    }
    return ret;
}

int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        FF(i, 1, n+1) scanf("%d", &a[i]), pos[a[i]] = i, c[i] = 0;
        REP(i, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
        sort(q, q+m);
        int j = 1;
        for(int i=0; i<m; )
        {
            if(q[i].r < j)
            {
                ans[q[i].id] = getsum(q[i].r) - getsum(q[i].l-1);
                i++;
            }
            else
            {
                add(j, 1);
                if(a[j] > 1 && pos[a[j]-1] < j) add(pos[a[j]-1], -1);
                if(a[j] < n && pos[a[j]+1] < j) add(pos[a[j]+1], -1);
                j++;
            }
        }
        REP(i, m) printf("%d\n", ans[i]);
    }
    return 0;
}