BZOJ3211: 花神游历各国

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

题解Here!

这是一道线段树的沙茶题。。。

然而我$WA+TLE$了无数发，原因是没有特判$0$。。。

我们发现$10^9$最多开个$5$次根号就会变成$1$。

于是用线段树暴力修改就好辣！

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) a[x].data
#define SIGN(x) a[x].flag
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)
#define MAXN 100010
using namespace std;
int n,m;
struct Segment_Tree{
    long long data;
    bool flag;
    int l,r;
}a[MAXN<<2];
inline long long read(){
	long long date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
inline void pushup(int rt){
    DATA(rt)=DATA(LSON)+DATA(RSON);
    SIGN(rt)=SIGN(LSON)&SIGN(RSON);
}
void buildtree(int l,int r,int rt){
    LSIDE(rt)=l;RSIDE(rt)=r;SIGN(rt)=false;
    if(l==r){
        DATA(rt)=read();
        if(DATA(rt)==0||DATA(rt)==1)SIGN(rt)=true;
        return;
    }
    int mid=l+r>>1;
    buildtree(l,mid,LSON);
    buildtree(mid+1,r,RSON);
    pushup(rt);
}
void update(int l,int r,int rt){
    if(SIGN(rt)||DATA(rt)==0)return;
    if(LSIDE(rt)==RSIDE(rt)){
        DATA(rt)=sqrt(DATA(rt));
        if(DATA(rt)==0||DATA(rt)==1)SIGN(rt)=true;
        return;
    }
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)update(l,r,LSON);
    if(mid<r)update(l,r,RSON);
    pushup(rt);
}
long long query(int l,int r,int rt){
    long long ans=0;
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA(rt);
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)ans+=query(l,r,LSON);
    if(mid<r)ans+=query(l,r,RSON);
    return ans;
}
void work(){
    int f,x,y;
    while(m--){
        f=read();x=read();y=read();
        if(x>y)swap(x,y);
        if(f==1)printf("%lld
",query(x,y,1));
        else update(x,y,1);
    }
}
void init(){
    n=read();
    buildtree(1,n,1);
    m=read();
}
int main(){
    init();
    work();
    return 0;
}