- Can you answer these querites?
- HDU - 4027
普通的线段树题, 但是有一个问题是, 区间更新时, 因为必须更新每个点, 才能更新区间, 那么线段树更新就很慢了, 无法使用 lazy 数组. 有一个小技巧是当区间和等于区间长度时, 那么说明已经到最好的情况了, 不用再修改了. 这一步简化后就可以过了
如果写线段树可以像喝水一样自然就好了
- #include <iostream>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- #define mem(x) memset(x,0,sizeof(x))
- using namespace std;
- typedef long long ll;
- const int INF=9999999;
- const int maxn=100000+5;
- ll sum[maxn<<2];
- int n;
- void pushup(ll rt){
- sum[rt]=sum[rt<<1]+sum[rt<<1|1];
- }
- void build(int l,int r,int rt){
- if(l==r){
- scanf("%lld",&sum[rt]);
- return;
- }
- int m=(l+r)>>1;
- build(lson);
- build(rson);
- pushup(rt);
- }
- void update(int L,int R,int l,int r,int rt){
- if(sum[rt]==r-l+1) return;
- if(l==r) {
- sum[rt]=(ll) sqrt(sum[rt]);
- return;
- }
- int m=(l+r)>>1;
- if(L<=m) update(L,R,lson);
- if(R>m)update(L,R,rson);
- pushup(rt);
- }
- ll query(int L,int R,int l,int r,int rt){
- if(L<=l&&R>=r){
- return sum[rt];
- }
- ll res=0;
- int m=(l+r)>>1;
- if(L<=m) res+=query(L,R,lson);
- if(R>m) res+=query(L,R,rson);
- return res;
- }
- int main(){
- int cnt=0;
- while(cin>>n){
- printf("Case #%d:\n",++cnt);
- build(1,n,1);
- int m;scanf("%d",&m);
- for(int i=1;i<=m;i++){
- int a,b,c;scanf("%d%d%d",&a,&b,&c);
- if(b>c) swap(b,c);
- if(a==1){
- printf("%lld\n",query(b,c,1,n,1));
- }
- else
- { update(b,c,1,n,1);
- }
- }
- cout <<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3128571.html