【UOJ#228】基础数据结构练习题

  • 本文为博主原创，未经许可不得转载

看到区间开根的时候我懵逼了，这tm怎么做

然后查看题解恍然大悟

把区间开根转化为区间减法就行了

具体做法：

如果当前区间满足$maxx-minn=\sqrt{maxx} - \sqrt{minn}$

那么当前区间满足区间减法的性质，直接打标记，否则递归左右子树

这种做法应该叫做吉司机线段树，时间复杂度$O(7mlogn)$

我也不会证明复杂度QAQ

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
using namespace std;
typedef long long ll;
struct node{ll maxx,minn,delta,sum;}tr[MAXN<<3];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void relord(int p){
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	tr[p].maxx=max(tr[p<<1].maxx,tr[p<<1|1].maxx);
	tr[p].minn=min(tr[p<<1].minn,tr[p<<1|1].minn);
}
void pushdown(int p,int l,int r){
	int mid=(l+r)>>1;
	if(tr[p].delta){
		ll temp=tr[p].delta;
		tr[p<<1].delta+=temp;  tr[p<<1|1].delta+=temp;
		tr[p<<1].maxx+=temp;   tr[p<<1|1].maxx+=temp;
		tr[p<<1].minn+=temp;   tr[p<<1|1].minn+=temp;
		tr[p<<1].sum+=temp*(mid-l+1);  tr[p<<1|1].sum+=temp*(r-mid);
		tr[p].delta=0;
	}
}
void build(int p,int l,int r){
	if(l==r){tr[p].sum=tr[p].maxx=tr[p].minn=read(); return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);  build(p<<1|1,mid+1,r);
	relord(p);
}
void add(int p,int l,int r,int x,int y,int v){
	pushdown(p,l,r);
	if(x<=l&&y>=r){
		tr[p].delta+=v; 
		tr[p].maxx+=v;
		tr[p].minn+=v;
		tr[p].sum+=(ll)v*(r-l+1); 
		return;
	}
	int mid=(l+r)>>1;  
	if(x<=mid) add(p<<1,l,mid,x,y,v);  
	if(y>mid)  add(p<<1|1,mid+1,r,x,y,v);
	relord(p);
}
void updata(int p,int l,int r,int x,int y){
	pushdown(p,l,r);
	if(x<=l&&y>=r&&tr[p].maxx-tr[p].minn==(ll)sqrt(tr[p].maxx)-(ll)sqrt(tr[p].minn)){
		ll v=(ll)sqrt(tr[p].maxx)-tr[p].maxx;
		tr[p].sum+=v*(r-l+1);
		tr[p].maxx+=v;
		tr[p].minn+=v;
		tr[p].delta+=v;
		return;
	}
	int mid=(l+r)>>1;  
	if(x<=mid) updata(p<<1,l,mid,x,y);  
	if(y>mid)  updata(p<<1|1,mid+1,r,x,y);
	relord(p);
}
ll query(int p,int l,int r,int x,int y){
	pushdown(p,l,r);
	if(x<=l&&y>=r) return tr[p].sum;
	int mid=(l+r)>>1; ll ret=0;
	if(x<=mid) ret+=query(p<<1,l,mid,x,y);
	if(y>mid)  ret+=query(p<<1|1,mid+1,r,x,y);
	return ret;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n=read(),m=read();  build(1,1,n);
	for(int i=1;i<=m;++i){
		int opt=read(),l=read(),r=read();
		if(opt==1){int x=read();add(1,1,n,l,r,x);}
		else if(opt==2)updata(1,1,n,l,r);
		else printf("%lld\n",query(1,1,n,l,r));
	}
	return 0;
}

本文标题:【UOJ#228】基础数据结构练习题

文章作者:chty

发布时间:2017年06月05日 - 20时57分

最后更新:2018年06月08日 - 18时45分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,