分析問題並考慮已知的數據結構。
細節處理很重要。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
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<b) return b;
else return a;
}
int min(int a,int b)
{
if(a<b) return a;
else return b;
}
int cmp(struct vv x,struct vv y)
{
return x.l<y.l;
}
int lowbit(int x)
{
return x&-x;
}
void update(int a,int b)
{
for(int i=a;i<=100005;i+=lowbit(i))
c[i]+=b;
}
int sum(int a)
{
int ret=0;
for(int i=a;i>=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<m;i++)
{
scanf("%d%d",&v[i].l,&v[i].r);
v[i].id=i;//利用這個Id進行編號是個好技巧...應該可以這麼輸出？
}
sort(v,v+m,cmp);
int i = 1;
int j = 0;
while(j < m) //m次詢問
{
while(i <= n && i < v[j].l) //從左到右刪除
{
if(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<m;i++)
printf("%d\n",ret[i]);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
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<b) return b;
else return a;
}
int min(int a,int b)
{
if(a<b) return a;
else return b;
}
int cmp(struct vv x,struct vv y)
{
return x.l<y.l;
}
int lowbit(int x)
{
return x&-x;
}
void update(int a,int b)
{
for(int i=a;i<=100005;i+=lowbit(i))
c[i]+=b;
}
int sum(int a)
{
int ret=0;
for(int i=a;i>=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<m;i++)
{
scanf("%d%d",&v[i].l,&v[i].r);
v[i].id=i;//利用這個Id進行編號是個好技巧...應該可以這麼輸出？
}
sort(v,v+m,cmp);
int i = 1;
int j = 0;
while(j < m) //m次詢問
{
while(i <= n && i < v[j].l) //從左到右刪除
{
if(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<m;i++)
printf("%d\n",ret[i]);
}
return 0;
}
