3211: 花神游历各国
Time Limit: 5 Sec Memory Limit: 128 MB Submit: 3514 Solved: 1306 [ ][ ][ ]Description
Input
Output
每次x=1时，每行一个整数，表示这次旅行的开心度
Sample Input
4 1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 1 1 4
Sample Output
101 11 11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
Source
题目链接：
分析：
题目这么长，其实就是2个操作：
1.询问L,R中的各个数之和
2.将L,R中的每个数x,将x修x1/2，向下取整。。
我们其实可以发现1000000000中的数修改不了几次就会变成1，那么直接暴力修改，若一段区间内的数全部<=1也就不用再改下去了。。
下面给出AC代码：
1 #include2 using namespace std; 3 inline int read() 4 { 5 int x=0,f=1; 6 char ch=getchar(); 7 while(ch<'0'||ch>'9') 8 { 9 if(ch=='-')10 f=-1;11 ch=getchar();12 }13 while(ch>='0'&&ch<='9')14 {15 x=x*10+ch-'0';16 ch=getchar();17 }18 return x*f;19 }20 const int N=100010;21 int n,m,pos,x,y;22 int a[N],add[N<<2];23 typedef long long ll;24 ll ans,sum[N<<2];25 inline void buildtree(int l,int r,int pos)26 {27 if(l==r)28 {29 sum[pos]=a[l];30 if(a[l]<=1)31 add[pos]=1;32 else33 add[pos]=0;34 return;35 }36 int mid=(l+r)/2;37 buildtree(l,mid,pos*2);38 buildtree(mid+1,r,pos*2+1);39 sum[pos]=sum[pos*2]+sum[pos*2+1];40 add[pos]=add[pos*2]&add[pos*2+1];41 }42 inline void update(int l,int r,int x,int y,int pos)43 {44 if(add[pos])45 return;46 if(l==r)47 {48 sum[pos]=(int)sqrt(sum[pos]);49 if(sum[pos]<=1)50 add[pos]=1;51 return;52 }53 int mid=(l+r)/2;54 if(x<=mid)55 update(l,mid,x,y,pos*2);56 if(y>mid)57 update(mid+1,r,x,y,pos*2+1);58 add[pos]=add[pos*2]&add[pos*2+1];59 sum[pos]=sum[pos*2]+sum[pos*2+1];60 }61 inline void solve(int l,int r,int x,int y,int pos)62 {63 if(x<=l&&r<=y)64 {65 ans+=sum[pos];66 return;67 }68 int mid=(l+r)/2;69 if(x<=mid)70 solve(l,mid,x,y,pos*2);71 if(y>mid)72 solve(mid+1,r,x,y,pos*2+1);73 }74 int main()75 {76 n=read();77 for(int i=1;i<=n;i++)78 a[i]=read();79 buildtree(1,n,1);80 m=read();81 for(int i=1;i<=m;i++)82 {83 pos=read();84 x=read();85 y=read();86 if(pos==1)87 {88 ans=0;89 solve(1,n,x,y,1);90 printf("%lld\n",ans);91 }92 else93 update(1,n,x,y,1);94 }95 return 0;96 }