HDU4638[离线树状数组]
分析问题并考虑已知的数据结构。
细节处理很重要。
#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;
}
补充：软件开发 , C++ ,
