「BZOJ3211」花神游历各国
Description
.jpg)
Input
.jpg)
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
题解
同上帝造题的七分钟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll a[100001];int n,m; struct data{ int l,r;ll sum; bool flag; }tr[400001]; void build(int k,int s,int t) { tr[k].l=s;tr[k].r=t; if(s==t){ tr[k].sum=a[s]; if(a[s]==1||a[s]==0)tr[k].flag=1; return; } int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; tr[k].flag=tr[k<<1].flag&tr[k<<1|1].flag; } void change(int k,int x,int y) { if(tr[k].flag)return; int l=tr[k].l,r=tr[k].r; if(l==r){ tr[k].sum=(ll)sqrt(tr[k].sum); if(tr[k].sum==1||tr[k].sum==0)tr[k].flag=1; return; } int mid=(l+r)>>1; if(mid>=y)change(k<<1,x,y); else if(mid<x)change(k<<1|1,x,y); else { change(k<<1,x,mid); change(k<<1|1,mid+1,y); } tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; tr[k].flag=tr[k<<1].flag&tr[k<<1|1].flag; } ll ask(int k,int x,int y) { int l=tr[k].l,r=tr[k].r; if(l==x&&r==y)return tr[k].sum; int mid=(l+r)>>1; if(mid>=y)return ask(k<<1,x,y); else if(mid<x)return ask(k<<1|1,x,y); else return ask(k<<1,x,mid)+ask(k<<1|1,mid+1,y); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { int k,x,y; scanf("%d%d%d",&k,&x,&y); if(x>y)swap(x,y); if(k==2)change(1,x,y); else printf("%lld\n",ask(1,x,y)); } return 0; } |
Subscribe
计数器 9788058
OI 课件=>
OI 课件=>