Fork me on GitHub

[UVa-12299] RMQ with Shifts 线段树单点修改区间查询

发表于 | 分类于
字数统计: 1,078字 | 阅读时长 ≈ 6分钟

题面

传送门: UVa-12299

题目大意:在传统的RMQ问题上多附加一个的操作,使得这些操作的数列轮换一位。

给出的规模是

样例

看传送门吧.

思路

但是,,输入中操作行的字符串长度小于等于30.

也就是说shift操作里的元素不会很多。

那么就暴力地上吧.

于是第一次写出来

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
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 1e5+10;
int n,q,a[maxn],b[maxn];
char req;
vector<int>r,w;
inline void read(int &x)
{
	x=0;char ch=getchar();if(ch=='\n'){x=-2333333;return;}int f=1;
	while(!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
struct SegmentTree{
	int lazy[maxn<<2],minv[maxn<<2];
	void pushup(int rt){minv[rt] = min(minv[lc],minv[rc]);}
	void build(int rt,int l,int r)
	{
		if (l == r)
		{
			minv[rt] = a[l];
			return ;
		}
		int m = (l+r) >> 1;
		build(lc,l,m);
		build(rc,m+1,r);
		pushup(rt);
	}
	void update(int p,int v,int L,int R,int rt) // LR修改区间 
	{
		if (L == R)
		{
			minv[rt] = v;
			return ;
		}
		int m = (L+R) >> 1;
		if(p <= m) update(p,v,L,m,lc);
		else update(p,v,m+1,R,rc);
		pushup(rt);
	}
	int query(int ql,int qr,int l,int r,int rt)
	{
		int ans = INT_MAX,m = (l+r)>>1;
		if (ql <= l && qr >= r) return minv[rt];
		if (ql <= m) ans = min(ans,query(ql,qr,l,m,lc));
		if (qr > m) ans = min(ans,query(ql,qr,m+1,r,rc));
		return ans;
	}
}Tree;

int main(int argc, char *argv[])
{
	read(n); read(q);
	for (int i = 1; i <= n; i++) read(a[i]);
	Tree.build(1,1,n);
	
	while(q--)
	{
		req = '6';
		memcpy(b,a,sizeof(a));
		while(!isalpha(req)) req = getchar();
		if (req == 'q') 
		{
			int x,y;
			read(x),read(y);
			printf("%d\n",Tree.query(x,y,1,n,1));
		} 
		
		else if (req == 's')
		{
			int x;
			r.clear();
			read(x);
			while(x!=-2333333)
			{
				r.push_back(x);
				read(x);
			}
			
			for (int i = 0; i < r.size(); i++)
			{
				//printf("Elements: ");
				//printf("%d ",r[i]);
				//puts("");
				if (i == r.size()-1) a[r[i]] = b[r[0]],Tree.update(r[i],b[r[0]],1,n,1);
				else a[r[i]] = b[r[i+1]],Tree.update(r[i],b[r[i+1]],1,n,1);
			}
		}
	}
	return 0;
}

中间字符串处理卡了好久哦.不得不在快读中加判断换行返回-2333333来皮一波.

但是T飞了..

Markdown

检查了半天没觉得哪里不对劲,然后尝试着把vector改成了定长数组,把memcpy去掉.

就过了..

实践证明,memcpy确实慢的可以.

代码

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
86
#include<bits/stdc++.h>
using namespace std;
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 1e5+10;
int n,q,a[maxn],b[maxn];
char req;
int r[41],w[41],cnt = 0;
inline void read(int &x)
{
	x=0;char ch=getchar();if(ch=='\n'){x=-2333333;return;}int f=1;
	while(!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
struct SegmentTree{
	int lazy[maxn<<2],minv[maxn<<2];
	void pushup(int rt){minv[rt] = min(minv[lc],minv[rc]);}
	void build(int rt,int l,int r)
	{
		if (l == r)
		{
			minv[rt] = a[l];
			return ;
		}
		int m = (l+r) >> 1;
		build(lc,l,m);
		build(rc,m+1,r);
		pushup(rt);
	}
	void update(int p,int v,int L,int R,int rt) // LR修改区间 
	{
		if (L == R)
		{
			minv[rt] = v;
			return ;
		}
		int m = (L+R) >> 1;
		if(p <= m) update(p,v,L,m,lc);
		else update(p,v,m+1,R,rc);
		pushup(rt);
	}
	int query(int ql,int qr,int l,int r,int rt)
	{
		int ans = INT_MAX,m = (l+r)>>1;
		if (ql <= l && qr >= r) return minv[rt];
		if (ql <= m) ans = min(ans,query(ql,qr,l,m,lc));
		if (qr > m) ans = min(ans,query(ql,qr,m+1,r,rc));
		return ans;
	}
}Tree;

int main(int argc, char *argv[])
{
	read(n); read(q);
	for (int i = 1; i <= n; i++) read(a[i]);
	Tree.build(1,1,n);
	
	while(q--)
	{
		req = '6';
		while(!isalpha(req)) req = getchar();
		if (req == 'q') 
		{
			int x,y;
			read(x),read(y);
			printf("%d\n",Tree.query(x,y,1,n,1));
		} 
		else if (req == 's')
		{
			int x;
			cnt = 0;
			read(x);
			while(x!=-2333333)
			{
				r[++cnt] = x;
				w[cnt] = a[x];
				read(x);
			}
			for (int i = 1; i <= cnt-1; i++)
				a[r[i]] = w[i+1],Tree.update(r[i],w[i+1],1,n,1);
			a[r[cnt]] = w[1],Tree.update(r[cnt],w[1],1,n,1);
		}
	}
	return 0;
}