HDU4638[离线树状数组]

分析问题并考虑已知的数据结构。

细节处理很重要。

#include    
#include    
#include    
#include    
#include    
using namespace std;  
//用标记数组的话果然不对  比如样例3 1 2 5 4，走一遍之后，再从头开始进行遍历的话，3+1，3-1都有标记，后面的都加了1   
//还有得注意到底是什么情况下用sum(a)-sum(b);什么情况下只用sum(a)就够了   
//树状数组更新之后 其后所有的数都会更新 切记   
int a[100005];  
int visit[100005];  
int c[100005];  
int ret[100005];  
int num[100005];  
struct vv  
{  
    int l,r;  
    int id;  
}v[100005];  
int max(int a,int b)  
{  
    if(a=1;i-=lowbit(i))  
        ret+=c[i];  
    return ret;  
}  
int main()  
{  
    int case_num;  
    scanf("%d",&case_num);  
    while(case_num--)  
    {  
        memset(c,0,sizeof(c));  
        memset(num,0,sizeof(num));  
        int n,m;  
        scanf("%d%d",&n,&m);  
        for(int i = 1;i <= n;i++)  
        {  
            scanf("%d",&a[i]);  
            num[a[i]]=i;  
        }  
        num[0] = n+10;  
        num[n+1] = n+10;  
        for(int i = 1;i <= n;i++)  
        {  
            if(i < num[a[i]-1] && i < num[a[i]+1])     //d段数加1   
                update(i,1);  
            else if(i > num[a[i]-1] && i > num[a[i]+1])   //段数减1   
                update(i,-1);  
        }  
        for(int i=0;i num[a[i]-1] && i > num[a[i]+1])   //删除a[i],则把原来加的一,减去   
                    update(i,-1);  
                else if(i < num[a[i]-1] && i < num[a[i]+1])  
                {  
                    int Min = min(num[a[i]-1],num[a[i]+1]);  
                    int Max = max(num[a[i]-1],num[a[i]+1]);  
                    update(i,-1);               //愿来加的一减去   
                    update(Min,1);              //少了a[i],则相应段数增加   
                    update(Max,1);              // . ...   
                }  
                else if(i < num[a[i]-1])  
                {  
                    update(i,-1);  
                    update(num[a[i]-1],1);  
                }  
                else  
                {  
                    update(i,-1);  
                    update(num[a[i]+1],1);  
                }  
                i++;  
            }  
                ret[v[j].id]= sum(v[j].r); //保存答案   
                j++;  
        }  
        for(int i=0;i
#include 
#include 
#include 
#include 
using namespace std;
//用标记数组的话果然不对  比如样例3 1 2 5 4，走一遍之后，再从头开始进行遍历的话，3+1，3-1都有标记，后面的都加了1
//还有得注意到底是什么情况下用sum(a)-sum(b);什么情况下只用sum(a)就够了
//树状数组更新之后 其后所有的数都会更新 切记
int a[100005];
int visit[100005];
int c[100005];
int ret[100005];
int num[100005];
struct vv
{
    int l,r;
    int id;
}v[100005];
int max(int a,int b)
{
    if(a=1;i-=lowbit(i))
        ret+=c[i];
    return ret;
}
int main()
{
    int case_num;
    scanf("%d",&case_num);
    while(case_num--)
    {
        memset(c,0,sizeof(c));
        memset(num,0,sizeof(num));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&a[i]);
            num[a[i]]=i;
        }
        num[0] = n+10;
        num[n+1] = n+10;
        for(int i = 1;i <= n;i++)
        {
            if(i < num[a[i]-1] && i < num[a[i]+1])     //d段数加1
                update(i,1);
            else if(i > num[a[i]-1] && i > num[a[i]+1])   //段数减1
                update(i,-1);
        }
        for(int i=0;i num[a[i]-1] && i > num[a[i]+1])   //删除a[i],则把原来加的一,减去
                    update(i,-1);
                else if(i < num[a[i]-1] && i < num[a[i]+1])
                {
                    int Min = min(num[a[i]-1],num[a[i]+1]);
                    int Max = max(num[a[i]-1],num[a[i]+1]);
                    update(i,-1);               //愿来加的一减去
                    update(Min,1);              //少了a[i],则相应段数增加
                    update(Max,1);              // . ...
                }
                else if(i < num[a[i]-1])
                {
                    update(i,-1);
                    update(num[a[i]-1],1);
                }
                else
                {
                    update(i,-1);
                    update(num[a[i]+1],1);
                }
                i++;
            }
                ret[v[j].id]= sum(v[j].r); //保存答案
                j++;
        }
        for(int i=0;i