UOJ228 基础数据结构练习题

题面：由于Paste下来太鬼，删了。

数据结构练习火题。。。。

WFJ大佬上午推荐了这道题，我就去做一做，然后一天就过去了。。。。

这里多了一个开根号的操作。。。变得很棘手

但其实可以发现这里面数的差会越来越小，当一个区间里所有数都一样时，开根号操作就可以转化成区间减去一个数a-sqrt(a)了。

所有数都一样，可转化为max==min判断。

然而有一个奇怪的优化。。。

如果min和max的差为1，且√max=√min+1,就可以优化。。。

然后就A了。。。

 1 // It is made by XZZ
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 #define rep(a,b,c) for(rg int a=b;a<=c;a++)
 7 #define drep(a,b,c) for(rg int a=b;a>=c;a--)
 8 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
 9 #define il inline
10 #define rg register
11 #define vd void
12 #define ls ((id)<<1)
13 #define rs ((id)<<1|1)
14 #define mid ((l+r)>>1)
15 typedef long long ll;
16 il int gi(){
17     rg int x=0,f=1;rg char ch=getchar();
18     while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
19     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
20     return x*f;
21 }
22 const int maxn=100001;
23 int L[maxn<<2],R[maxn<<2];
24 ll num[maxn<<2],Max[maxn<<2],Min[maxn<<2],lazy[maxn<<2];
25 
26 il vd build(int l,int r,int id){
27     L[id]=l,R[id]=r;
28     if(l==r)num[id]=Max[id]=Min[id]=(ll)gi();
29     else build(l,mid,ls),build(mid+1,r,rs),num[id]=num[ls]+num[rs],Max[id]=max(Max[ls],Max[rs]),Min[id]=min(Min[ls],Min[rs]);
30 }
31 
32 il vd down(int id){
33     if(L[id]==R[id])return;
34     num[ls]+=lazy[id]*(R[ls]-L[ls]+1);
35     if(L[ls]-R[ls])Max[ls]+=lazy[id],Min[ls]+=lazy[id];
36     else Max[ls]=Min[ls]=num[ls];
37     lazy[ls]+=lazy[id];
38     num[rs]+=lazy[id]*(R[rs]-L[rs]+1);
39     if(L[rs]-R[rs])Max[rs]+=lazy[id],Min[rs]+=lazy[id];
40     else Max[rs]=Min[rs]=num[rs];
41     lazy[rs]+=lazy[id];
42     lazy[id]=0;
43 }
44 
45 il vd update_add(int id,int l,int r,ll Num){
46     down(id);
47     if(L[id]>=l&&R[id]<=r){num[id]+=Num*(R[id]-L[id]+1),Max[id]+=Num,Min[id]+=Num,lazy[id]=Num;return;}
48     if(R[ls]>=l)update_add(ls,l,r,Num);
49     if(L[rs]<=r)update_add(rs,l,r,Num);
50     num[id]=num[ls]+num[rs],Max[id]=max(Max[ls],Max[rs]),Min[id]=min(Min[ls],Min[rs]);
51 }
52 
53 il vd update_sqrt(int id,int l,int r){
54     down(id);
55     if((L[id]>=l&&R[id]<=r)&&(Max[id]==Min[id]||(Max[id]==Min[id]+1&&(ll)sqrt(Max[id])==(ll)sqrt(Min[id])+1))){update_add(id,l,r,(ll)sqrt(Max[id])-Max[id]);return;}
56     if(R[ls]>=l)update_sqrt(ls,l,r);
57     if(L[rs]<=r)update_sqrt(rs,l,r);
58     num[id]=num[ls]+num[rs],Max[id]=max(Max[ls],Max[rs]),Min[id]=min(Min[ls],Min[rs]);
59 }
60 
61 il ll query(int id,int l,int r){
62     down(id);
63     if(L[id]>=l&&R[id]<=r)return num[id];
64     if(R[ls]<l)return query(rs,l,r);
65     else if(L[rs]>r)return query(ls,l,r);
66     else return query(ls,l,r)+query(rs,l,r);
67 }
68 
69 int main(){
70     rg int n=gi(),m=gi();
71     build(1,n,1);
72     rg int k,l,r;
73     while(m--){
74     k=gi(),l=gi(),r=gi();
75     switch(k){
76     case 1:update_add(1,l,r,(ll)gi());break;
77     case 2:update_sqrt(1,l,r);break;
78     case 3:printf("%lld\n",query(1,l,r));break;
79     }
80     }
81     return 0;
82 }

View Code

PS.好久没打线段树了。。。

秒客网

UOJ228 基础数据结构练习题

相关文章