Post 7

Veröffentlicht am | Edited on

过程和结局都有了、再去纠缠、连自己都觉得贪婪。

「一本通 5.6 例 2」任务安排 3

输入格式

第一行两个整数，分别为 N,SN,S；
接下来 NN 行每行两个整数 T_i,C_iTi​,Ci​。

数据范围与提示

对于全部数据，

题解

这道题的斜率不再单增，但是后面的表达式依然与

单调。

所以我们依旧维护每个点

的斜率单调，使用单调栈即可，由于需要支持随机访问栈中元素，请手写一个栈。

然后二分一个最“凸”点即可。

二分边界细节及其恶心，这次终于靠着大量调试代码1个小时内调试出来了。

按照格式输出大量调试信息！

Code：

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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 300005
#define LL long long
LL f[maxn] , t[maxn] , s[maxn];
int n , T;
struct Stack
{
	int l , r , p[maxn];
    Stack(){
		l = 1 , r = 0;
		std::memset(p,0,sizeof(p));
	}
	inline void push_back(int x){
		p[++r] = x;
	}
	inline void pop_back(){
		p[r] = 0; --r;
	}
	inline int size(){
		return r - l + 1;
	}
	inline int& operator[](int x){
		return p[r-x+1];
	}
	inline int& operator()(int x){
		return p[l+x-1];
	}
	inline int calc(int k)
	{
		//puts("The find of");
		int curL = l , curR = r;
		while(curL <= curR)
		{
			int mid = curL + curR >> 1;
			if(mid == l && f[p[mid+1]]-f[p[mid]] > k*(s[p[mid+1]]-s[p[mid]]))	return p[mid];
			else if(mid == l && f[p[mid+1]]-f[p[mid]] <= k*(s[p[mid+1]]-s[p[mid]]))	return p[mid+1];
			if(mid == r && f[p[mid]]-f[p[mid-1]] < k*(s[p[mid]]-s[p[mid-1]])) return p[mid];
			else if(mid == r && f[p[mid]]-f[p[mid-1]] >= k*(s[p[mid]]-s[p[mid-1]]))	return p[mid-1];
		
			if(f[p[mid]]-f[p[mid-1]]<k*(s[p[mid]]-s[p[mid-1]])&&f[p[mid+1]]-f[p[mid]]<k*(s[p[mid+1]]-s[p[mid]])) curL=mid+1;
			else if(f[p[mid]]-f[p[mid-1]]<=k*(s[p[mid]]-s[p[mid-1]])&&f[p[mid+1]]-f[p[mid]]>=k*(s[p[mid+1]]-s[p[mid]]))
			   	return p[mid];
			else curR=mid-1;
		}
	}
	inline void DEBUG()
	{
		puts("DEBUG");
		puts("Size");
		printf("%d\n",r-l+1);
		puts("THE ELEMENTS");
		for(int i = l ; i <= r ; ++i)
			printf("%d ",p[i]);
		puts("THE SLOPE");
		for(int i = l ; i < r ; ++i)
			if(s[p[i+1]] != s[p[i]])
				printf("%.2lf\n",(double)(f[p[i+1]]-f[p[i]])/(s[p[i+1]]-s[p[i]]));
			else puts("0");
	}
}q;
int main()
{
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		t[i]=t[i-1]+x;
		s[i]=s[i-1]+y;
	}
	f[0]=0;
	q.push_back(0);
	for(int i=1;i<=n;++i)
	{
		int k;
		k = q.calc(T+t[i]);
	//	printf("The Transfer Point:%d\n",k);
		f[i] = f[k]+T*(s[n]-s[k])+t[i]*(s[i]-s[k]);
	//	printf("The Best Cost:%lld\n",f[i]);
	//	printf("The Query Slope: %lllld\n",T+t[i]);
	//	q.DEBUG();
	//	printf("The cur Slope:%.2lf\n",(double)(f[i]-f[q[1]])/(s[i]-s[q[1]]));
	//	puts("FINISH");
	//	putchar(10);
		while(q.size()>1&&1ll*(f[i]-f[q[1]])*(s[q[1]]-s[q[2]])<=1ll*(f[q[1]]-f[q[2]])*(s[i]-s[q[1]]))
			q.pop_back();
		q.push_back(i);
	}
	printf("%lld\n",f[n]);
}

[USACO16OPEN]248

题目描述

Bessie likes downloading games to play on her cell phone, even though she doesfind the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing.The game starts with a sequence of NN positive integers (2 \leq N\leq 2482≤N≤248), each in the range 1 \ldots 401…40. In one move, Bessie cantake two adjacent numbers with equal values and replace them a singlenumber of value one greater (e.g., she might replace two adjacent 7swith an 8). The goal is to maximize the value of the largest numberpresent in the sequence at the end of the game. Please help Bessiescore as highly as possible!

给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。

输入输出格式

输入格式：

The first line of input contains NN, and the next NN lines give the sequence

of NN numbers at the start of the game.

输出格式：

Please output the largest integer Bessie can generate.

输入输出样例

输入样例#1：

1
2
3
4
5
4
1
1
1
2

输出样例#1：

1
3

说明

In this example shown here, Bessie first merges the second and third 1s to

obtain the sequence 1 2 2, and then she merges the 2s into a 3. Note that it is

not optimal to join the first two 1s.

题解

一个还算可以的区间dp？
我们不能设

表示i~j内能合成的最大数，而是设

表示这个区间最后合成了什么数（最大的那个数一定是一个连续的区间通过某种顺序合并的），然后标记一下那些数出现过。即可

Code：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 305
int f[maxn][maxn] , n , p[maxn];
bool mark[maxn];
int main()
{
	std::memset(f,-0x7f,sizeof(f));
	scanf("%d",&n);
	for(int i = 1 ; i <= n; ++i){
		int x;
		scanf("%d",&x);
		f[i][i] = x;
		p[i] = x;
	}
	for(int k = 2 ; k <= n ; ++k)
		for(int i = 1 ; i <= n - k + 1; ++i)
		{
			int fr = i , to = i + k - 1;
			for(int j = fr ; j < to ; ++j)
				if(f[fr][j] > 0 && f[j+1][to] > 0 && f[fr][j] == f[j+1][to])
					f[fr][to] = std::max(f[fr][to] , f[fr][j] + 1) , mark[f[fr][to]] = true;
		}
	for(int i = 40 ; i >= 1 ; --i)
		if(mark[i])
		{
			printf("%d",i);
			break;
		}
}

[USACO16OPEN]262144

题目描述

Bessie likes downloading games to play on her cell phone, even though she doesfind the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing.The game starts with a sequence of NN positive integers (2 \leq N\leq 262,1442≤N≤262,144), each in the range 1 \ldots 401…40. In one move, Bessiecan take two adjacent numbers with equal values and replace them asingle number of value one greater (e.g., she might replace twoadjacent 7s with an 8). The goal is to maximize the value of thelargest number present in the sequence at the end of the game. Pleasehelp Bessie score as highly as possible!

Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。

她被她最近玩的一款游戏迷住了，游戏一开始有n个正整数，(2<=n<=262144)，范围在1-40。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个7合并成一个8)，目标是使得最大的数最大，请帮助Bessie来求最大值。

输入输出格式

输入格式：

The first line of input contains NN, and the next NN lines give the sequence

of NN numbers at the start of the game.

输出格式：

Please output the largest integer Bessie can generate.

输入输出样例

输入样例#1：

1
2
3
4
5
4
1
1
1
2

输出样例#1：

1
3

说明

In this example shown here, Bessie first merges the second and third 1s to

obtain the sequence 1 2 2, and then she merges the 2s into a 3. Note that it is

not optimal to join the first two 1s.

题解

这个数据范围似乎要求更高效的算法了。。

从上题的思考过程中我们发现它实际上是连续的区间，只不过是按照某种顺序合并的。

然后题意又说两个相同的数合成大1的数，那这不很像倍增吗。。

所以我们记录每个位置合成每个数的右端点在哪，难想吗？挺难想。。（想出一半还是看了题解。。。）

转移到是很好想，当前位置若由比当前数小1的合成，位置就是

主要是状态难以思考出来。。

Code:

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 300005
int f[60][maxn], n;
bool mark[106];
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i){
        int x;
        scanf("%d", &x);
        f[x][i] = i + 1;
    }
	for(int i = 1 ; i <= 59 ; ++i)
		for(int j = 1 ; j <= n ; ++j)
		{
			if(!f[i][j])	f[i][j] = f[i-1][f[i-1][j]];
			if(f[i][j]) mark[i] = true;
		}
	for(int i = 59 ; i >= 1 ; --i)
		if(mark[i]){
			printf("%d",i);
			break;
		}
}

[USACO16OPEN]分割田地Splitting the Field

题目描述

Farmer John’s NN cows (3 \leq N \leq 50,0003≤N≤50,000) are all located at distinct positions in his two-dimensional field. FJ wants to enclose all of the cows with a rectangular fence whose sides are parallel to the x and y axes, and hewants this fence to be as small as possible so that it contains every cow (cowson the boundary are allowed).

FJ is unfortunately on a tight budget due to low milk production last quarter.He would therefore like to enclose a smaller area to reduce maintenance costs,and the only way he can see to do this is by building two enclosures instead of one. Please help him compute how much less area he needs to enclose, in total,by using two enclosures instead of one. Like the original enclosure, the two enclosures must collectively contain all the cows (with cows on boundaries allowed), and they must have sides parallel to the x and y axes. The two enclosures are not allowed to overlap — not even on their boundaries. Note that enclosures of zero area are legal, for example if an enclosure has zero width and/or zero height.在一个二维的牧场中，Farmer John的N（3<=N<=50000）头牛都各占一席。他想用边平行于x轴和y轴的矩形围栏围住所有牛，并且要让围栏尽可能小（牛可以在边界线上）。

不幸地，由于Farmer John的奶牛产量惨淡，导致最后一个季度预算紧张。因此，他希望封闭一个较小的地区来减少维修的费用，他能看到的唯一方法就是修建两个围栏而不是建一个。请编程告诉他用两个围栏比用一个围栏总共能够节省多少需要围住的面积。同样地，用两个围栏的时候必须围住所有的牛（牛同样可以在边界上），边也要平行于x轴和y轴。两个围栏不允许重叠（边界也不能）。注意面积为零是合法的，例如一个围栏有着长度为零的宽或长度为零的长（一条线）。

输入输出格式

输入格式：

The first line of input contains NN. The next NN lines each contain two

integers specifying the location of a cow. Cow locations are positive integers

in the range 1 \ldots 1,000,000,0001…1,000,000,000.

输出格式：

Write a single integer specifying amount of total area FJ can save by using two

enclosures instead of one.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
6
4 2
8 10
1 1
9 12
14 7
2 3

输出样例#1：

1
107

题解

一道简单的排序题。

显然对于一些点用一个最小矩形覆盖就是

所以一个矩形覆盖的面积如何计算就不用说了。

那么两个矩形最优情况是什么呢？

一定是在那些点中间分开的两部分！这完全就是画图可知。。。

那么我们是可以O(n)枚举这些矩形组合情况的。

首先按x坐标排序。

然后预处理出

分别表示前k个点纵坐标最大最小值，后k个点纵坐标最大最小值。

那么每次是可以O(1)计算每种矩形组合的面积的，取最小值。

完了吗?当然没有，我们还可以横着分！。

再按y坐标排序，然后相同做法一直取最小值。

一开始居然把单调队列写错了，不该写那个没用的pop_front()

Code：

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 50005
#define LL long long
int fmax[maxn] , fmin[maxn] , gmax[maxn] , gmin[maxn] , n;
LL S1 , S2 , ymax , ymin;
struct Queue
{
    int p[maxn] ,l ,r;
    Queue(){
        l = 1 , r = 0;
        std::memset(p,0,sizeof(p));
    }
    inline void push_back(int x){
        p[++r] = x;
    }
    inline void pop_front(){
        p[l++]=0;
    }
    inline void pop_back(){
        p[r--] = 0;
    }
    inline int size(){
        return r -l + 1;
    }
    inline int front(){
        return p[l];
    }
    inline int back(){
        return p[r];
    }
    inline void clear(){
        std::memset(p,0,sizeof(p));
        l = 1 , r = 0;
    }
}qmax , qmin;
struct Node{
    int x , y;
    bool operator < (const Node& p)const{
        return x < p.x;
    }
}t[maxn];
bool cmp(Node a , Node b){
    return a.y < b.y;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d%d",&t[i].x,&t[i].y);
    std::sort(t+1,t+n+1);
//	puts("Sorted by x");
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d%c",t[i].y,(i==n)?10:32);
    qmax.push_back(1);
    qmin.push_back(1);
    fmax[1]=fmin[1]=t[1].y;
    for(int i = 2 ; i <= n ; ++i){
        int now = t[i].y;
        while(qmax.size() && t[qmax.back()].y <= now)  qmax.pop_back();
        qmax.push_back(i);
        fmax[i]=t[qmax.front()].y;
        while(qmin.size() && t[qmin.back()].y >= now) qmin.pop_back();
        qmin.push_back(i);
        fmin[i]=t[qmin.front()].y;
    }
    qmax.clear();
    qmin.clear();
    qmax.push_back(n);
    qmin.push_back(n);
    gmin[n]=gmax[n]=t[n].y;
    for(int i = n - 1; i >= 1 ; --i)
    {
        int now = t[i].y;
        while(qmax.size() && t[qmax.back()].y <= now)	qmax.pop_back();
        qmax.push_back(i); 
        gmax[i]=t[qmax.front()].y;
        while(qmin.size() && t[qmin.back()].y >= now) qmin.pop_back();
        qmin.push_back(i);
        gmin[i]=t[qmin.front()].y;
    }
//	puts("By sorted x , the vals are");
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d %d %d %d\n",fmin[i],fmax[i],gmin[i],gmax[i]);
    S1 = 0x7ffffffffffffffLL , S2 = 0x7ffffffffffffffLL;
    int maxx = -0x7fffffff , minn = 0x7fffffff;
    for(int i = 1 ; i <= n ; ++i)
        maxx = std::max(maxx , t[i].y) , minn = std::min(minn , t[i].y);
    S1 = 1ll * (t[n].x - t[1].x) * (maxx - minn);
    for(int i = 1 ; i < n ; ++i)
        if(t[i].x != t[i+1].x)
            S2=std::min(S2,(LL)(1ll*(t[i].x-t[1].x)*(fmax[i]-fmin[i])+1ll*(t[n].x-t[i+1].x)*(gmax[i+1]-gmin[i+1])));
    std::sort(t+1,t+n+1,cmp);
//	puts("By sorted y , the Vals are");
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d%c",t[i].x,(i==n)?10:32);
    qmin.clear();
    qmax.clear();
    qmin.push_back(1);
    qmax.push_back(1);
    fmin[1] = fmax[1] = t[1].x;
    for(int i = 2 ; i <= n ; ++i)
    {
        while(qmax.size() && t[qmax.back()].x <= t[i].x)	qmax.pop_back();
        qmax.push_back(i);
        fmax[i]=t[qmax.front()].x;
        while(qmin.size() && t[qmin.back()].x >= t[i].x) qmin.pop_back();
        qmin.push_back(i);
        fmin[i] = t[qmin.front()].x;
    }
    qmax.clear();
    qmin.clear();
    qmax.push_back(1), qmin.push_back(1);
    gmin[n] = gmax[n] = t[n].x;
    for(int i=n-1;i>=1;--i)
    {
        while(qmax.size() && t[qmax.back()].x <= t[i].x) qmax.pop_back();
        qmax.push_back(i);
        gmax[i]=t[qmax.front()].x;
        while(qmin.size() && t[qmin.back()].x >= t[i].x) qmin.pop_back();
        qmin.push_back(i);
        gmin[i]=t[qmin.front()].x;
    }
    //puts("By sorted y , the vals are");
    //for(int i = 1 ; i <= n ; ++i)
    //	printf("%d %d %d %d\n",fmin[i],fmax[i],gmin[i],gmax[i]);
    for(int i = 1 ; i < n ; ++i)
        if(t[i].y != t[i+1].y)
            S2=std::min(S2,1ll*(t[i].y-t[1].y)*(fmax[i]-fmin[i])+1ll*(t[n].y-t[i+1].y)*(gmax[i]-gmin[i]));
    printf("%lld",S1-S2);
    
}

P2647 最大收益

题目描述

现在你面前有n个物品，编号分别为1，2，3，……，n。你可以在这当中任意选择任意多个物品。其中第i个物品有两个属性Wi和Ri，当你选择了第i个物品后，你就可以获得Wi的收益；但是，你选择该物品以后选择的所有物品的收益都会减少Ri。现在请你求出，该选择哪些物品，并且该以什么样的顺序选取这些物品，才能使得自己获得的收益最大。

注意，收益的减少是会叠加的。比如，你选择了第i个物品，那么你就会获得了Wi的收益；然后你又选择了第j个物品，你又获得了Wj-Ri收益；之后你又选择了第k个物品，你又获得了Wk-Ri-Rj的收益；那么你获得的收益总和为Wi+(Wj-Ri)+(Wk-Ri-Rj)。

输入输出格式

输入格式：

第一行一个正整数n，表示物品的个数。

接下来第2行到第n+1行，每行两个正整数Wi和Ri，含义如题目所述。

输出格式：

输出仅一行，表示最大的收益。

输入输出样例

1
2
3
2
5 2
3 5
1
6

说明

20%的数据满足：n<=5，0<=Wi,Ri<=1000。

50%的数据满足：n<=15，0<=Wi,Ri<=1000。

100%的数据满足：n<=3000，0<=Wi,Ri<=200000。

样例解释：我们可以选择1号物品，获得了5点收益；之后我们再选择2号物品，获得3-2=1点收益。最后总的收益值为5+1=6。

题解

是道贪心+dp。。。

有个看上去很套路的DP：

设前i件物品选j件的最优值是多少。

但是这样很明显是不正确的。

然后写出转移：

对于确定的j，我们总是希望他的

尽可能小，也就是说对于大的j，

要小

因此从大到小排序。

证明：考虑对题目进行一个等价的变换：即选择某个物品后，选择该物品前所有选择的物品的收益减少Ri。

假设存在顺序对，交换后必定不劣。满足决策单调性。

Code：

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 <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 3005
int n , ans , f[maxn][maxn];
inline int max(int x, int y,int z)
{
    int k = x > y ? x :y;
    return k > z ? k : z;
}
struct Node{
    int x , y;
 	bool operator<(const Node& a)const{
        return y > a.y;
    }
}p[maxn];
int main()
{
    scanf("%d",&n);
    for(int  i =1 ; i <= n ; ++i)
        scanf("%d%d",&p[i].x,&p[i].y);
    std::sort(p+1,p+n+1);
    for(int i = 1; i <= n ; ++i)
        f[i][i]=p[i].x;
    for(int i = 1; i <= n ; ++i)
        for(int j = 1 ; j <= i ; ++j)
            f[i][j]=max(f[i-1][j],f[i-1][j-1]+p[i].x-p[i].y*(j-1),f[i][j-1]) , ans = std::max(ans , f[i][j]);
    printf("%d\n",ans);
}

[JSOI2008]最大数

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1、 查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：LL不超过当前数列的长度。(L > 0)(L>0)

2、 插入操作。

语法：A n

功能：将nn加上tt，其中tt是最近一次查询操作的答案（如果还未执行过查询操作，则t=0t=0)，并将所得结果对一个固定的常数DD取模，将所得答案插入到数列的末尾。

限制：nn是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入输出格式

输入格式：

第一行两个整数，MM和DD，其中MM表示操作的个数(M \le 200,000)(M≤200,000)，DD如上文中所述，满足(0<D<2,000,000,000)(0<D<2,000,000,000)

接下来的MM行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式：

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 100
A 96
Q 1
A 97
Q 1
Q 2

输出样例#1：

1
2
3
96
93
96

说明

[JSOI2008]

题解

本题仅仅练手，没有任何难度。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
#define LL long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
LL m , lastans , mod;
struct SegmentTree
{
	LL maxx[maxn<<2] , pos;
	inline void pushup(int node){
		maxx[node] = std::max(maxx[ls(node)] , maxx[rs(node)]);
	}
	inline void insert(int p , int l , int r , int node , LL v){
		if(l == r)
		{
			maxx[node] = v;
			return;
		}
		int mid = l + r >> 1;
		if(p <= mid) insert(p , l , mid , ls(node) , v);
		else insert(p , mid +1 , r , rs(node) , v);
		pushup(node);
	}
	inline LL queryMax(int L , int R , int l , int r , int node)
	{
		if(L <= l && r <= R)
			return maxx[node];
		int mid = l + r >> 1;
		LL ans = -0x7fffffffffffffffLL;
		if(L <= mid) ans = std::max(ans , queryMax(L , R , l , mid , ls(node)));
		if(R > mid) ans = std::max(ans , queryMax(L , R , mid + 1 , r , rs(node)));
		return ans;
	}
	inline LL query(int l)
	{
		return queryMax(pos-l+1,pos,1,m,1);
	}
}sgt;
int main()
{
	scanf("%lld%lld",&m,&mod);
	for(int i = 1 ; i <= m ; ++i)
	{
		char ch;
		std::cin >> ch;
		if(ch == 'Q'){
			int L;	
			scanf("%d",&L);
			printf("%lld\n",lastans = sgt.query(L));
		}
		if(ch == 'A')
		{
			LL t;
			scanf("%lld",&t);
			t = (t + lastans) % mod;
			sgt.insert(++sgt.pos,1,m,1,t);
		}
	}
}

有点累了不写了，学学数学了。

今天海星，调个题都挺迅速，明天又到了大周呢！