BZOJ1012最大数maxnumber 做题笔记

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1012

这题每次都只查看最后l位的最大值，因而位置靠后的数如果大于前面的数，则前面的数是没有用的，直接扔掉即可。这样维护了一个单调递减的栈，同时再维护一个同步的位置栈，查询时需要根据位置栈找到所需最大值的位置，输出对应的最大值即可。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200009;
int q[N],pos[N];
int t=0;

int main() {
	char ch;
	int m,d;
	int x,tmp,p;
	int last=0;
	int tot=0;
	scanf("%d%d%*c",&m,&d);
	for (int i=0;i<m;i++) {
		scanf("%c%d%*c",&ch,&x);
		if (ch=='A') {
			tmp=(x+last)%d;
			while (t&&tmp>=q[t-1]) t--;
			pos[t]=tot++;
			q[t++]=tmp;
		}
		else {
			p=lower_bound(pos,pos+t,tot-x)-pos;
			last=q[p];
			printf("%d\n",last);
		}
	}
}

另外这题可以用线段树来做，先开好M大小的线段树，每次加节点时在后面插即可。

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int t=0;
int D=0;

struct Node {
	int m,lc,rc;
}node [1000000];

void build (int now,int l,int r) {
	node[now].m=0;
	if (l<r-1) {
		int mid=(l+r)>>1;
		node[now].lc=t;
		build(t++,l,mid);
		node[now].rc=t;
		build(t++,mid,r);
	}else {
		node[now].lc=node[now].rc=0;
	}
}

void change (int now,int l,int r,int lr,int delta) {
	if (lr<=l&&r<=lr+1) {
		node[now].m=max(node[now].m,delta);
		return;
	}
	int mid=(l+r)>>1;
	if (lr<mid) change(node[now].lc,l,mid,lr,delta);
	if (mid<lr+1) change(node[now].rc,mid,r,lr,delta);
	node[now].m=max(node[node[now].lc].m,node[node[now].rc].m);
}

int query (int now,int l,int r,int lr,int rr) {
	if (lr<=l&&r<=rr) {
		return node[now].m;
	}
	int mid=(l+r)>>1;int ans=0;
	if (lr<mid) ans=max(ans,query(node[now].lc,l,mid,lr,rr));
	if (mid<rr) ans=max(ans,query(node[now].rc,mid,r,lr,rr));
	return ans;
}

int main () {
	int m,tot=0,x;
    int last=0,tmp=0;
    char ch;
	scanf("%d%d%*c",&m,&D);
	int root=t++;
	build(root,0,m+1);
    for (int i=0;i<m;i++) {
        scanf("%c%d%*c",&ch,&x);
        if (ch=='A') {
            tmp=((long long)last+x)%D;
            change(root,0,m+1,tot,tmp);
            tot++;
        }
        else {
            printf("%d\n",last=query(root,0,m+1,tot-x,tot));
        }
    }
}