1.hdu1166
单点修改、区间和查询
注意：用位运算符的话要加最新标准的#include<string>头文件，否则编译错误，数组开4*n大小（还是不够熟练）
#include <iostream>
#include <string>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <ctype.h>
#include <map>
#include <queue>
#include <stack>
#define maxn 4*50005//开四倍！！
typedef long long ll;
using namespace std;
ll a[maxn],sum[maxn];
void update(ll i)
{
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void build(ll l,ll r,ll i)
{
if(l==r)
{
sum[i]=a[l];
return ;
}
ll mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
update(i);
}
ll query(ll l,ll r,ll x,ll y,ll i)
{
if(x<=l && r<=y)
return sum[i];
ll mid=(l+r)>>1,ans=0;
if(x<=mid) ans+=query(l,mid,x,y,i<<1);
if(y>=mid+1) ans+=query(mid+1,r,x,y,i<<1|1);
return ans;
}
void change(ll pos,ll v,ll l,ll r,ll i)
{
if(l==r)
{
sum[i]=sum[i]+v;
return ;
}
ll mid=(l+r)>>1;
if(pos<=mid) change(pos,v,l,mid,i<<1);
else change(pos,v,mid+1,r,i<<1|1);
update(i);
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
ll n,t,num=0,pos,v,x,y;
string s;
scanf("%lld",&t);
while(t--)
{
memset(sum,0,sizeof(sum));
printf("Case %lld:\n",++num);
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,n,1);
while(cin>>s && s!="End")
{
if(s=="Query")
{
scanf("%lld %lld",&x,&y);
printf("%lld\n",query(1,n,x,y,1));
}
if(s=="Add"||s=="Sub")
{
scanf("%lld %lld",&pos,&v);
if(s=="Add")
change(pos,v,1,n,1);
else
change(pos,-v,1,n,1);
}
}
}
return 0;
} 2.POJ3468
区间修改，区间和查询（要在蓝书代码的基础上做一点修改，改了半天5555）
#include <iostream>
#include <string>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <ctype.h>
#include <map>
#include <queue>
#include <stack>
#define maxn 4*111111//开四倍
typedef long long ll;
using namespace std;
ll a[maxn]={0},sum[maxn]={0},add[maxn]={0},sumv[maxn]={0};
void update(ll i,ll l,ll r)
{
if(r>l)
sum[i]=sumv[i<<1]+sumv[i<<1|1];//上一次操作后当前区间的值
sumv[i]=sum[i]+add[i]*(r-l+1);//注意这个变化是在sum[i]的基础上，因为add[i]是累加的！
}
void build(ll l,ll r,ll i)
{
if(l==r)
{
sum[i]=a[l];
return ;
}
ll mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void change(ll v,ll i,ll l,ll r,ll x,ll y)//修改区间（x,y）
{
if(x<=l && r<=y)//递归边界
{
add[i]+=v;
}
else
{
ll mid=(l+r)>>1;
if(x<=mid) change(v,i<<1,l,mid,x,y);
if(y>=mid+1) change(v,i<<1|1,mid+1,r,x,y);
}
update(i,l,r);
}
ll query(ll i,ll l,ll r,ll x,ll y,ll ad)
{
if(x<=l && r<=y)
{
return sumv[i]+ad*(r-l+1);
}
ll mid=(l+r)>>1,ans=0;
if(x<=mid) ans+=query(i<<1,l,mid,x,y,ad+add[i]);
if(y>=mid+1) ans+=query(i<<1|1,mid+1,r,x,y,ad+add[i]);
return ans;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
ll n,q,v,x,y;
char ch;
scanf("%lld %lld",&n,&q);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,n,1);
memcpy(sumv,sum,sizeof(sum));
while(q--)
{
cin>>ch;
if(ch=='Q')
{
scanf("%lld %lld",&x,&y);
printf("%lld\n",query(1,1,n,x,y,0));
}
else
{
scanf("%lld %lld %lld",&x,&y,&v);
change(v,1,1,n,x,y);
}
}
return 0;
} 这个才是真正的模版：注意scanf ch的时候要用getchar（）
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctype.h>
#define maxn 400005
typedef long long ll;
using namespace std;
ll add[maxn]={0},sum[maxn]={0},a[maxn]={0};
void pushup(ll i)
{
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void pushdown(ll i,ll l,ll r)//由父节点更新子结点的信息,并将父结点的懒人标记值置为0
{
ll mid=(l+r)>>1;
sum[i<<1]+=add[i]*(mid-l+1);
sum[i<<1|1]+=add[i]*(r-mid);
add[i<<1]+=add[i];
add[i<<1|1]+=add[i];
add[i]=0;
}
void build(ll i,ll l,ll r)
{
if(l==r)
sum[i]=a[l];
else
{
ll mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
}
void update(ll i,ll l,ll r,ll x,ll y,ll v)//把（x,y）范围内的数都增加v
{
if(x<=l && r<=y)
{
add[i]+=v;
sum[i]+=v*(r-l+1);
}
else
{
if(add[i]) pushdown(i,l,r);
ll mid=(l+r)>>1;
if(x<=mid) update(i<<1,l,mid,x,y,v);
if(y>mid) update(i<<1|1,mid+1,r,x,y,v);
pushup(i);
}
}
ll query(ll i,ll l,ll r,ll x,ll y)//(x,y)和
{
if(x<=l && r<=y)
return sum[i];
ll mid=(l+r)>>1,ans=0;
if(add[i]) pushdown(i,l,r);
if(x<=mid) ans+=query(i<<1,l,mid,x,y);
if(y>mid) ans+=query(i<<1|1,mid+1,r,x,y);
return ans;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
ll n,q,x,y,v;
char ch;
scanf("%lld %lld",&n,&q);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
while(q--)
{
cin>>ch;
//getchar();
if(ch=='Q')
{
scanf("%lld %lld",&x,&y);
printf("%lld\n",query(1,1,n,x,y));
}
else
{
scanf("%lld %lld %lld",&x,&y,&v);
//cout<<x<<y<<v<<endl;
update(1,1,n,x,y,v);
}
}
return 0;
} 3.hdu1698
区间赋值，区间求和
只需要在第二题的代码中稍微修改一下就可以了，因为是区间赋值，所以add和sum不需要累加，直接用=就可以啦
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctype.h>
#define maxn 400005
typedef long long ll;
using namespace std;
ll add[maxn]={0},sum[maxn]={0},a[maxn]={0};
void pushup(ll i)
{
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void pushdown(ll i,ll l,ll r)//由父节点更新子结点的信息,并将父结点的懒人标记值置为0
{
ll mid=(l+r)>>1;
sum[i<<1] = add[i]*(mid-l+1);
sum[i<<1|1] = add[i]*(r-mid);
add[i<<1] = add[i];
add[i<<1|1] = add[i];
add[i]=0;
}
void build(ll i,ll l,ll r)
{
if(l==r)
sum[i]=1;
else
{
ll mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
}
void update(ll i,ll l,ll r,ll x,ll y,ll v)//把（x,y）范围内的数都增加v
{
if(x<=l && r<=y)
{
add[i] = v;
sum[i] = v*(r-l+1);
}
else
{
if(add[i]) pushdown(i,l,r);
ll mid=(l+r)>>1;
if(x<=mid) update(i<<1,l,mid,x,y,v);
if(y>mid) update(i<<1|1,mid+1,r,x,y,v);
pushup(i);
}
}
ll query(ll i,ll l,ll r,ll x,ll y)//(x,y)和
{
if(x<=l && r<=y)
return sum[i];
ll mid=(l+r)>>1,ans=0;
if(add[i]) pushdown(i,l,r);
if(x<=mid) ans+=query(i<<1,l,mid,x,y);
if(y>mid) ans+=query(i<<1|1,mid+1,r,x,y);
return ans;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
ll t,n,q,x,y,v,num=0;
scanf("%lld",&t);
while(t--)
{
memset(add,0,sizeof(add));
memset(sum,0,sizeof(sum));
scanf("%lld",&n);
build(1,1,n);
scanf("%lld",&q);
while(q--)
{
scanf("%lld %lld %lld",&x,&y,&v);
update(1,1,n,x,y,v);
}
printf("Case %lld: The total value of the hook is %lld.\n",++num,sum[1]);
}
return 0;
}
京公网安备 11010502036488号