发表于 | 更新于

神奇的一届Noip。。第一天被T2吓晕却还是弄到了200+，第二天居然A了T3。。感觉难度分配真是不合理。

day 0

和同学一起去新建的乒乓球馆抽了签（话说之前根本不知道有个新建的乒乓球馆。。），天阴了下来，下起了毛毛雨。然后散了。

东校的基本都回家了，莒县的去了东阶。我背着电脑去看考场。

我抽到了2015年暑假刚开始学习OI时呆的机房。现在满满的回忆。仍然能记得曾经在哪个位置坐着谁，记得当时一下课就一窝蜂地窜下楼打篮球，回来之后被老师批判一番……曾经的naive freshmen已经变成了学长，而且也只剩下了为数不多的几人。而已经有了一等准备继续下去的只有我一个了，这次比赛之后，我应该就是我们年级唯一的OIer了。

回了趟教室打了杯水，同学们起哄地鼓掌，险些起飞。迅速逃走。

然后去了东阶。暂时还只有莒县的同学在那里。打开电脑写起了高精——上一次联赛之前我也是在写高精，因为平时用得少，考试的时候一旦写不出来就麻烦了。写了一个有点丧病的支持正负数的+-，发现也不是那么好写的。去年联赛之前写乘法都是很无知地模拟竖式，用到高精×单精和高精+。。。被管爷教育了一番才学会了用类似卷积的办法直接计算。

下午各省的神陆续驾到。人群中看到了dms、汪啸宇和（被学妹簇拥着的）Menci，还有slyz的对不上号的ShallWe和BeiYu和DaD3zZ。瞬间感觉自己十分渺小。

试机。写了一遍Treap，随机数生成器，对拍自动机，拍了一会儿整数排序。GDB，G++什么的看起来一切正常，新电脑的键盘鼠标也很舒服。

day 1

到校很早，一直在机房门口等着思考人生。

发题。按照一般的经验，day1应该能很快第干掉1、2，剩下大部分时间杠3。于是这就成了我day1挂掉的原因。 T1 Mogician？Mengbier？不吐槽了，写完完事。

T2 树上问题？Interesting。Noip day1 T2考树，也就是个简单的树归什么的？发现并不会O(n)O(n)地表示出状态。于是先写了30分打算用来对拍。

路径？按套路点分治什么的？可发现好像各个点的答案没法再分治过程中统计。思索良久，无果。改变策略看T3。

T3 期望？DP？然后整个人都不好了，直接慌掉了。

直观感受一下应该是存在最优子结构的，于是写DP。写到一半，感觉自己对期望的性质了解太少，不敢随便写，于是就还是暴力吧。0 1 2的写完之后就完事了。然而悲催的是，n=2000被我理解成点数，觉得没戏直接没开到2000，白白丢了不少暴力分。

回去做T2。链用一个双指针，S=1用DFS序树状数组统计答案，然后就没有然后了。拍着，没出什么问题。但这道题数据随机的话应该不会测出什么问题。所以考完之后感觉很虚。

下午听莒县的一个同学说暴力分有244？

下午在东阶研究了一下dflasher的模版，写了写哈希表之类的小东西。

晚上调整，看了几集憨豆先生。

day 2

考完day1之后觉得要AFO了，心态也就放松了不少。

T1 递推前缀和，然后对拍，结果到了30就出问题了，结果发现时到了30就爆LL了。。不怎么会python，也没辙了，只好一直放10+的数据对拍，无语。。

T2 上来就写了O(nlogn)O(n log n)的暴力。

T3 直接爆搜吧。搜完之后发现最大的一组样例很慢，于是就加了状压剪枝。加上之后才发现好像可以直接状压DP。。。naive。。不管了。

after

之后一周一直处在惶恐之中，做梦都是哪里的细节写挂了。其中梦到了floyd没清对角线，结果还就真没清。

周日晚上发现群里说凌晨出成绩，就等到了凌晨，结果凌晨官网准时被黑。WOC。等了一会儿，最后还是睡了。

周一一天都在教室的电脑上刷rg.noi，结果一直是可恶的lalala。。。真。。。

到了晚上我都已经不抱希望了，去问同级的同学有没有什么确切消息。惊闻成绩已出。

窜回教室，查到成绩，456。还算可以吧。于是课间顺利起飞。

after after

不算上集训队队员的话就是第十了。虽然不是很靠前，但也完成了预期的目标。于是就确定下来要继续走这条路。

最近高三的王浩然大神刚刚得了NMO的Au。学校已经好多年没出过竞赛的Au了。大概有了他的引领，我们这些人会得到更多的支持吧。

不管如何，自己选择的路，跪着也要走完

发表于 | 更新于

做法

之前学习树套树的时候，用线段树套线段树卡时限过了。 暑假的时候学CDQ分治，但不知为什么没写个整体二分的题目。就拿来练手了。 由于过于蒟蒻，看别人的代码也没有完全看懂，于是就结合对CDQ分治的理解类比写了一个。然后挂了。 然后发现是线段树写错了。每次时间戳更新之后，在修改节点的时候是在访问到之后才清空的。这样就导致了每个点都有一个子节点还存着之前的值，向上传递的时候就WA了。 然而我改对了线段树，依然WA。找到ZJOI的数据，A了。看到Discuss区里僧仙提示了一组数据，于是把各种可疑的变量都改成了long long，依然WA。WA了一晚上，我索性把CA爷的代码交了上去，居然也WA了。在网上找了好久才找到一个没有WA的，脑洞一开把这人的fread优化粘贴上，于是就A了。至今不知道怎么回事。 实现的时候为了方便，在读入数据的时候就把K大转化成K小。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cassert>
//define red(x) scanf("%d",&x)
static const int S = 1310720;
 
inline int get_char() {
    static char buf[S];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, S, stdin);
    if (pos == len) return -1;
    return buf[pos++];
}
 
template<class T> inline
void red(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}

const int MAXN=50000+100;
typedef long long LL;
const LL INF=3000000000LL;

struct SegmentTree
{
	struct SegNode
	{
		int us;
		LL cnt,mrk;
	}seg[MAXN<<2];
	int TL,TR,timeline;
	SegmentTree(){timeline=0;}
	inline void Init(int x)
	{
		TL=1;
		TR=x;
	}
	inline void dispose(int pos)
	{
		if(seg[pos].us!=timeline)
		{
			seg[pos].us=timeline;
			seg[pos].cnt=0;
			seg[pos].mrk=0;
		}
	}
	void markdown(int pos,int L,int R)
	{
		dispose(pos<<1);
		dispose(pos<<1|1);
		if(seg[pos].mrk)
		{
			seg[pos<<1].mrk+=seg[pos].mrk;
			seg[pos<<1|1].mrk+=seg[pos].mrk;
			int MID=(L+R)>>1;
			seg[pos<<1].cnt+=(LL)seg[pos].mrk*(MID-L+1);
			seg[pos<<1|1].cnt+=(LL)seg[pos].mrk*(R-MID);
			seg[pos].mrk=0;	
		}
	}
	void Edit(int pos,int L,int R,int l,int r,int v)
	{
		dispose(pos);
		if(L==l && R==r)
		{
			seg[pos].mrk+=v;
			seg[pos].cnt+=(LL)(R-L+1)*v;
		}
		else
		{
			markdown(pos,L,R);
			int MID=(L+R)>>1;
			if(r<=MID)
				Edit(pos<<1,L,MID,l,r,v);
			else if(MID+1<=l)
				Edit(pos<<1|1,MID+1,R,l,r,v);
			else
				Edit(pos<<1,L,MID,l,MID,v),
				Edit(pos<<1|1,MID+1,R,MID+1,r,v);
			seg[pos].cnt=seg[pos<<1].cnt+seg[pos<<1|1].cnt;
		}
	}
	void Edit(int l,int r,int v)
	{
		Edit(1,TL,TR,l,r,v);
	}
	LL Access(int pos,int L,int R,int l,int r)
	{
		if(seg[pos].us!=timeline)
			return 0;
		if(L==l && R==r)
			return seg[pos].cnt;
		else
		{
			markdown(pos,L,R);
			int MID=(L+R)>>1;
			if(r<=MID)
				return Access(pos<<1,L,MID,l,r);
			else if(MID+1<=l)
				return Access(pos<<1|1,MID+1,R,l,r);
			else
				return Access(pos<<1,L,MID,l,MID)
					  +Access(pos<<1|1,MID+1,R,MID+1,r);
		}
	}
	inline LL Access(int l,int r)
	{
		return Access(1,TL,TR,l,r);
	}
	inline void Clear()
	{
		timeline++;
	}
}T;
struct Query
{
	int kd,l,r,id;
	LL k;
	bool operator <(const Query& x) const
	{
		return id<x.id;
	}
}p[MAXN],t[MAXN];
int ANS[MAXN];
void DC(int low,int high,int L,int R)
{
	if(L>R)
		return;
	if(low==high)
	{
		for(int i=L;i<=R;i++)
			if(p[i].kd==2)
				ANS[p[i].id]=low;
		return;
	}
	std::sort(p+L,p+R+1);
	T.Clear();
	LL mid=(low+high)>>1;
	int l=L-1,r=R+1;
	LL res;
	for(int i=L;i<=R;i++)
	{
		if(p[i].kd==1)
		{
			if(p[i].k<=mid)
			{
				T.Edit(p[i].l,p[i].r,1);
				t[++l]=p[i];
			}
			else
				t[--r]=p[i];
		}
		else
		{
			res=T.Access(p[i].l,p[i].r);
			if(p[i].k<=res)
				t[++l]=p[i];
			else
			{
				p[i].k-=res;
				t[--r]=p[i];
			}
		}
	}
	for(int i=L;i<=R;i++) p[i]=t[i];
	DC(low,mid,L,l);
	DC(mid+1,high,r,R);	
}

int main()
{
//	freopen("input.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;red(n),red(m);
	T.Init(n);
	T.Clear();
	for(int i=1;i<=m;i++)
	{
		red(p[i].kd),red(p[i].l),red(p[i].r),red(p[i].k);
		p[i].id=i;
		ANS[i]=-MAXN;
		if(p[i].kd==1)
			T.Edit(p[i].l,p[i].r,1);
		else
			p[i].k=(LL)T.Access(p[i].l,p[i].r)-p[i].k+1;
	}
	DC(-n,n,1,m);
	for(int i=1;i<=m;i++)
		if(ANS[i]!=-MAXN)
			printf("%d\n",ANS[i]);

	return 0;
}

附上树套树 

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 50100
#define MAXND MAXN*650
#define N 50000
#define S(X,NUMO) seg[X].son[NUMO]
int n,m;
int L[MAXN*10],R[MAXN*10],RT[MAXN*10];int o=0;

struct SegNode
{
	int son[2],cnt,mark;
	SegNode()
	{
		son[0]=son[1]=cnt=mark=0;
	}
}seg[MAXND];int pc=0;
inline void checks(int pos)
{
	if(!S(pos,0)) S(pos,0)=++pc;
	if(!S(pos,1)) S(pos,1)=++pc;
}
void markdown(int pos,int be,int en)
{
	if(be!=en)
	{
		checks(pos);
		if(seg[pos].mark)
		{
			int mid=(be+en)>>1;
			seg[S(pos,0)].cnt+=(mid-be+1)*seg[pos].mark;
			seg[S(pos,1)].cnt+=(en-mid)*seg[pos].mark;
			seg[S(pos,0)].mark+=seg[pos].mark;
			seg[S(pos,1)].mark+=seg[pos].mark;
			seg[pos].mark=0;
		}
	}
	else return;
}

void Build(int pos,int l,int r)
{
	L[pos]=l;R[pos]=r;
	RT[pos]=++pc;
	if(l!=r)
	{
		int mid=(l+r)>>1;
		Build(pos<<1,l,mid);
		Build(pos<<1|1,mid+1,r);
	}
}

void ins(int pos,int be,int en,int l,int r)
{
	markdown(pos,be,en);
	if(l==be && r==en)
	{
		seg[pos].cnt+=(en-be+1);
		seg[pos].mark++;
	}
	else
	{
		
		int mid=(be+en)>>1;
		if(r<=mid) ins(S(pos,0),be,mid,l,r);
		else if(mid+1<=l) ins(S(pos,1),mid+1,en,l,r);
		else
		{
			ins(S(pos,0),be,mid,l,mid);
			ins(S(pos,1),mid+1,en,mid+1,r);
		}
		seg[pos].cnt=seg[S(pos,0)].cnt+seg[S(pos,1)].cnt;
	}
}
void INS(int pos,int l,int r,int num)
{
	if(L[pos]!=R[pos])
	{
		int mid=(L[pos]+R[pos])>>1;
		if(num<=mid) INS(pos<<1,l,r,num);
		else INS(pos<<1|1,l,r,num);
	}
	ins(RT[pos],1,n,l,r);
}

int acs(int pos,int be,int en,int l,int r)
{
	//if(pos==0)
	//	return 0;
	markdown(pos,be,en);
	if(l==be && en==r)
	{
		return seg[pos].cnt;
	}
	else
	{
		int mid=(be+en)>>1;
		if(r<=mid) return acs(S(pos,0),be,mid,l,r);
		else if(l>=mid+1) return acs(S(pos,1),mid+1,en,l,r);
		else 
			return acs(S(pos,0),be,mid,l,mid)
				  +acs(S(pos,1),mid+1,en,mid+1,r);
	}
}

int ACS(int pos,int l,int r,int K)
{
	int res=acs(RT[1],1,n,l,r);

	K=res-K+1;
	res=0;
	while(L[pos]!=R[pos])
	{
		res=acs(RT[pos<<1],1,n,l,r);
		if(res<K)
		{
			K-=res;
			pos=pos<<1|1;
		}
		else pos=pos<<1;
	}	
	return L[pos];
}
int Que(int l,int r,int K)
{
	return ACS(1,l,r,K);	
} 
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%d%d",&n,&m);
	Build(1,-N,N);
	int opt,t1,t2,t3;
	for(int i=1;i<=m;i++)
	{
	//	printf("%d\n",i);
		scanf("%d%d%d%d",&opt,&t1,&t2,&t3);
		if(opt==1)//ins
			INS(1,t1,t2,t3);
		else
		{
			printf("%d\n",Que(t1,t2,t3));
		}
	}
	
	
	return 0;
}

发表于 | 更新于

题目

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 n 杯鸡尾酒。这 n 杯鸡尾酒排成一行，其中第 i 杯酒 （1≤i≤n） 被贴上了一个标签 si，每个标签都是 26 个小写英文字母之一。设 Str(l,r) 表示第 l 杯酒到第 r 杯酒的 r−l+1 个标签顺次连接构成的字符串。若 Str(p,po)=Str(q,qo)，其中 1≤p≤po≤n，1≤q≤qo≤n，p≠q，po−p+1=qo−q+1=r，则称第 p 杯酒与第 q 杯酒是“r相似” 的。当然两杯“r相似” （r>1）的酒同时也是“1 相似”、“2 相似”、…、“(r−1) 相似”的。特别地，对于任意的 1≤p,q≤n，p≠q，第 p 杯酒和第 q 杯酒都是“0相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 i 杯酒 （1≤i≤n） 的美味度为 ai。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 p 杯酒与第 q 杯酒调兑在一起，将得到一杯美味度为 apaq 的酒。现在请各位品酒师分别对于 r=0,1,2,…,n−1，统计出有多少种方法可以选出 2 杯“r相似”的酒,并回答选择 2 杯“r相似”的酒调兑可以得到的美味度的最大值。

做法

分开看这两问。先建出后缀数组。

第一问，可以用单调栈处理出每个height[]height[]覆盖的区间，即预处理出ls[i]ls[i]和rs[i]rs[i]分别表示左右第一个比height[i]height[i]小的位置。扫一遍统计答案。

but对于我们这些蒟蒻。这一问我都不会做。

一开始想的是每个ii对答案的贡献是(i−(ls[i]+1)+1)∗((rs[i]−1)−i+1)−1(i-(ls[i]+1)+1)*((rs[i]-1)-i+1)-1，然而我并没有理解heightheight的含义。

右区间不包含中点。中点与右区间的LCP不是中点的height。 第二问就用一个线段树或者ST表维护区间最大最小值，左右区间的最大最小值依次相乘，最大值肯定在这四个之中。

但是！

我的后缀数组被卡常数了！我还需要怎么优化！罗大神的代码根本看不懂啊！ uoj过了，在BZOJ卡了一上午，换成ST表，各种卡卡卡，都TLE了

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
typedef long long LL;
const int MAXN=300000+100;
const int INF=2e9;
const LL INFXINF=2e18;
char s[MAXN];
int height[MAXN],rnk[MAXN],sa[MAXN];
inline LL max(const LL &a,const LL &b)
{
    return a<b?b:a;
}
inline LL min(const LL &a,const LL &b)
{
    return b<a?b:a;
}
struct Tripple
{
    int a,b,id;
    bool operator <(const Tripple& x)const
    {
        if(a!=x.a)
            return a<x.a;
        return b<x.b;
    }
};
inline bool equal(Tripple *x,Tripple *y)
{
    return x->a==y->a && x->b==y->b;
}
 
void Da(int n)
{
    static Tripple t[MAXN],*p[MAXN],*q[MAXN];
    static int rc[MAXN];
    for(int i=1;i<=n;i++)
        t[i].a=s[i]-'a'+1,t[i].id=i;
    std::sort(t+1,t+1+n);
    for(int i=1,c=0;i<=n;i++)
        rnk[t[i].id]=t[i].a==t[i-1].a?c:++c;
    for(int l=1;l<n;l<<=1)
    {
        for(int i=1;i<=n;i++)
        {
            t[i].a=rnk[i];
            t[i].b=i+l<=n?rnk[i+l]:0;
            t[i].id=i;
            p[i]=&t[i];
        }
        memset(rc,0,sizeof(rc[0])*(n+1));
        for(int i=1;i<=n;i++)
            rc[p[i]->b]++;
        for(int i=1;i<=n;i++)
            rc[i]+=rc[i-1];
        for(int i=n;i;i--)
            q[rc[p[i]->b]--]=p[i];
        memset(rc,0,sizeof(rc[0])*(n+1));
        for(int i=1;i<=n;i++)
            rc[q[i]->a]++;
        for(int i=1;i<=n;i++)
            rc[i]+=rc[i-1];
        for(int i=n;i;i--)
            p[rc[q[i]->a]--]=q[i];
        rnk[p[1]->id]=1;
        for(int i=2,c=1;i<=n;i++)
            rnk[p[i]->id]=equal(p[i],p[i-1])?c:++c;
    }
    for(int i=1;i<=n;i++)
        sa[rnk[i]]=i;
    for(int i=1,j,L=0;i<=n;i++)
    {
        if(rnk[i]!=1)
        {
            j=sa[rnk[i]-1];
            while(s[i+L]==s[j+L])//i+L+1..
                L++;
            height[rnk[i]]=L;
            if(L)
                L--;
        }
    }
}
int ls[MAXN],rs[MAXN],v[MAXN];
void Stack(int n)
{
    height[0]=height[n+1]=-INF;
    ls[1]=0;
    for(int i=2,j;i<=n;i++)
    {
        j=i-1;
        while(height[i]<height[j])
            j=ls[j];
        ls[i]=j;
    }
    rs[n]=n+1;
    for(int i=n-1,j;i;i--)
    {
        j=i+1;
        while(height[i]<=height[j])
            j=rs[j];
        rs[i]=j;
    }
}
struct SegNode
{
    int mx,mn;
    SegNode(int _x=-INF,int _n=INF)
    {
        mx=_x;
        mn=_n;
    }
}seg[MAXN*4];
SegNode operator +(const SegNode &a,const SegNode &b)
{
    return SegNode(max(a.mx,b.mx),min(a.mn,b.mn));
}
void Build(int pos,int L,int R)
{
    if(L==R)
        seg[pos].mx=seg[pos].mn=v[L];
    else
    {
        int MID=(L+R)>>1;
        Build(pos<<1,L,MID);
        Build(pos<<1|1,MID+1,R);
        seg[pos]=seg[pos<<1]+seg[pos<<1|1];
    }
}
LL cnt[MAXN],w[MAXN];
SegNode Access(int pos,int L,int R,int l,int r)
{
    if(L==l && R==r)
        return seg[pos];
    else
    {
        int MID=(L+R)>>1;
        if(r<=MID)
            return Access(pos<<1,L,MID,l,r);
        else if(MID+1<=l)
            return Access(pos<<1|1,MID+1,R,l,r);
        else
            return Access(pos<<1,L,MID,l,MID)+Access(pos<<1|1,MID+1,R,MID+1,r);
    }
}
inline LL Deal(SegNode a,SegNode b)
{
    LL ANS=-INFXINF;
    ANS=max(ANS,(LL)a.mx*b.mx);
    ANS=max(ANS,(LL)a.mn*b.mn);
    // positive
    ANS=max(ANS,(LL)a.mx*b.mn);
    ANS=max(ANS,(LL)a.mn*b.mx);
    // negative   
    return ANS;
}
int main()
{
    //freopen("input.txt","r",stdin);    freopen("ox.txt","w",stdout);
    int n;
    red(n);
    scanf("%s",s+1);
    Da(n);
    Stack(n);
    w[0]=-INFXINF;
    for(int i=1,x;i<=n;i++)
    {
        red(x);
        v[rnk[i]]=x;   
        w[i]=-INFXINF;
    }
    Build(1,1,n);
    for(int i=2,l,r;i<=n;i++)
    {
        cnt[height[i]]+=(LL)(i-ls[i])*(rs[i]-i);
        w[height[i]]=max(w[height[i]],Deal(Access(1,1,n,ls[i],i-1),Access(1,1,n,i,rs[i]-1)));
    }
    for(int i=n-1;~i;i--)cnt[i]+=cnt[i+1],w[i]=max(w[i],w[i+1]);
    for(int i=0;i<n;i++)
        printf("%lld %lld\n",cnt[i],cnt[i]?w[i]:0);
    return 0;
}

发表于 | 更新于

这是第二场codeforces。第一场codeforces因为在做CPU监控，拖了半个小时才开始做题。上次的BC，过了三道题的PT然后全都FST。每次的线上赛都惨不忍睹，不知道这次会怎么样。

A

打开题目吓了一跳，什么鬼？看不懂？然后在我仔细理解题意的时候已经有好多人A了。我吓到了，直接看样例，发现似乎是个编程入门题。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
const int MAXN=100+2;
char s[MAXN];
int c[MAXN];
int main()
{
	//freopen("input.txt","r",stdin);
	int n;red(n);
	scanf("%s",s+1);
	int bc=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='B')
			c[s[i]==s[i-1]?bc:++bc]++;
	}
	printf("%d\n",bc);
	if(bc)
	{
		for(int i=1;i<bc;i++)
			printf("%d ",c[i]);
		printf("%d\n",c[bc]);
	}

	return 0;
}

B

题意好理解，公式随便一写。 

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
const int MAXN=100+2;
char s[MAXN];
int cnt[MAXN];
int main()
{
//	freopen("input.txt","r",stdin);
	int n,k;red(n),red(k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		cnt[strlen(s+1)]++;
	}
	scanf("%s",s+1);
	int ans=strlen(s+1);
	int x=0;
	int sum=0;
	for(int i=1;i<ans;i++)
		sum+=cnt[i];
	x=sum+(sum/k)*5;
	printf("%d ",x+1);
	sum+=cnt[ans];
	x=sum+((sum-1)/k)*5;
	printf("%d\n",x);
	return 0;
}

C

限时+经过城市最多，我一眼就看着像网络流。于是就死磕网络流，怎么都建不出图。于是比赛结束了。看了看大神的代码。什么！直接O(n2)O(n^2)DP？直接SPFA？直接拓扑序？凌乱。。

教训

  • 永远不要质疑CF评测机的速度
  • 在DAG上DP是很正常的思路

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include <queue>
#define red(x) scanf("%d",&x)
using std::queue;

const int MAXN=5000+10;
struct Edge
{
	int to,v;	
}e[MAXN];int pre[MAXN],id[MAXN],ec=0;
int f[MAXN][MAXN],pr[MAXN][MAXN];
int n,T;
void adde(int _f,int _t,int _v)
{
	e[++ec].to=_t;e[ec].v=_v;pre[ec]=id[_f];id[_f]=ec;
}
int ind[MAXN];
void BFS()
{
	queue<int> Q;
	memset(f,127,sizeof(f));
	f[1][1]=0;
	for(int i=1;i<=n;i++)
		if(!ind[i])
			Q.push(i);
	while(!Q.empty())
	{
		int pres=Q.front();Q.pop();
		for(int i=id[pres],u;i;i=pre[i])
		{
			u=e[i].to;
			if(!--ind[u])
				Q.push(u);
			for(int j=2;j<=n;j++)
				if(f[pres][j-1]<=T)
				{
					if(f[pres][j-1]+e[i].v<f[u][j])
						f[u][j]=f[pres][j-1]+e[i].v,
						pr[u][j]=pres;
				}
		}
	}
}
void print(int pos,int c)
{
	if(!pos)
		return;
	print(pr[pos][c],c-1);
	printf("%d ",pos);
}
int main()
{
	//freopen("input.txt","r",stdin);
	int m;
	red(n),red(m),red(T);
	for(int i=1,t1,t2,t3;i<=m;i++)
	{
		red(t1),red(t2),red(t3);
		adde(t1,t2,t3);ind[t2]++;
	}
	BFS();
	int ans=-1;
	for(int i=n;i;i--)
		if(f[n][i]<=T)
		{
			ans=i;
			break;
		}
	if(ans!=-1)
	{
		printf("%d\n",ans);
		print(pr[n][ans],ans-1);
		printf("%d\n",n);
	}
	return 0;
}

发表于 | 更新于

序列莫队的复杂度证明

讨论

  1. 对于同一块内的所有询问，右端点的移动是O(n)O(n)的，左端点的移动是O(n)×O(n)=O(n)O(\sqrt n) \times O(\sqrt n)=O(n)
  2. 对于qiq_i和qi+1q_{i+1}再不在同一块中的询问，左端点移动O(n)O(\sqrt n)，右端点移动O(n)O(n)。这样的询问一共有n\sqrt n个。总复杂度为n×(O(n)+O(n))=O(nn)\sqrt n \times (O(\sqrt n)+O(n))=O(n\sqrt n)

总复杂度为O(nn)O(n\sqrt n)

思考

再确定莫队以后，要想怎样才能减小转移的时间消耗。比如，在我看来，树上莫队要用DFSDFS序的话就会很慢，因为块内的节点可能隔的很远，而且可能排成很长的一条链。

发表于 | 更新于

题意

输入一个nm的矩阵，矩阵的每一个元素都是一个整数，然后有q个询问，每次询问一个子矩阵的权值。矩阵的权值是这样定义的，对于一个整数x，如果它在该矩阵中出现了p次，那么它给该矩阵的权值就贡献p2。

做法

题意描述是标准的莫队。但因为是矩阵，那就是二维莫队咯。 考虑一下，应该让块紧凑一些，转移复杂度会比较小，因此这个的分块就相当于横切几刀竖切几刀分成的块。 类比序列的莫队，(i,j)(i,j)位置所在的块为([i−1n]+1−1)m+[j−1m]+1([\frac {i-1}{\sqrt n}]+1-1)\sqrt m+[\frac {j-1}{\sqrt m}]+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
94
95
96
97
98
99
100
101
102
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <utility>
#define red(x) scanf("%d",&x)
const int MAXN=200+1;
const int MAXQ=100000+1;
inline int sqr(const int& x)
{
	return x*x;
}
int rf[MAXN][MAXN],v[MAXN][MAXN],lis[MAXN*MAXN],bn[MAXN][MAXN],ANS[MAXQ];
struct Query
{
	int id,x1,y1,x2,y2;
	bool operator <(const Query& a) const
	{
		if(bn[x1][y1]!=bn[a.x1][a.y1])
			return bn[x1][y1]<bn[a.x1][a.y1];
		return rf[x2][y2]<rf[a.x2][a.y2];
	}
}q[MAXQ];int qc;
int cnt[MAXN*MAXN],ans;
inline void mod(int x,int y,int d)
{
	ans-=sqr(cnt[v[x][y]]);
	cnt[v[x][y]]+=d;
	ans+=sqr(cnt[v[x][y]]);
}
inline void ModifyX(int x,int b,int t,int d)
{
	for(int i=t;i<=b;i++)
		mod(x,i,d);
}
inline void ModifyY(int y,int l,int r,int d)
{
	for(int i=l;i<=r;i++)
		mod(i,y,d);
}
void Mo()
{
	int x1=1,x2=1,y1=1,y2=1;
	cnt[v[1][1]]=1;
	ans=1;
	for(int i=1;i<=qc;i++)
	{
		while(x1>q[i].x1)
			ModifyX(--x1,y2,y1,1);
		while(x2<q[i].x2)
			ModifyX(++x2,y2,y1,1);
		while(y1>q[i].y1)
			ModifyY(--y1,x1,x2,1);
		while(y2<q[i].y2)
			ModifyY(++y2,x1,x2,1);

		while(x1<q[i].x1)
			ModifyX(x1++,y2,y1,-1);
		while(x2>q[i].x2)
			ModifyX(x2--,y2,y1,-1);
		while(y1<q[i].y1)
			ModifyY(y1++,x1,x2,-1);
		while(y2>q[i].y2)
			ModifyY(y2--,x1,x2,-1);
		ANS[q[i].id]=ans;	
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int n,m,t1,t2,t3;red(n),red(m);
	int ns=sqrt(n),ms=sqrt(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			red(t1);
			lis[rf[i][j]=(i-1)*m+j]=v[i][j]=t1;
			bn[i][j]=(((i-1)/ns+1)-1)*ms+(j-1)/ms+1;
		}
	int lisc=m*n;
	std::sort(lis+1,lis+1+lisc);
	lisc=std::unique(lis+1,lis+1+lisc)-lis-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			v[i][j]=std::lower_bound(lis+1,lis+1+lisc,v[i][j])-lis;
	red(qc);
	for(int i=1;i<=qc;i++)
	{
		red(q[i].x1),red(q[i].y1),red(q[i].x2),red(q[i].y2);
		if(q[i].x1>q[i].x2)
			std::swap(q[i].x1,q[i].x2);
		if(q[i].y1>q[i].y2)
			std::swap(q[i].y1,q[i].y2);
		q[i].id=i;
	}
	std::sort(q+1,q+1+qc);
	Mo();
	for(int i=1;i<=qc;i++)
		printf("%d\n",ANS[i]);
	return 0;
}

发表于 | 更新于

题意

给定同余方程组xi≡kixpi+bix_i \equiv k_ix_{p_i}+b_i，要求支持如下操作

  • 输出xix_i
  • 修改一个方程

做法

从四月开始学LCT就想做的题目，现在总算A掉了十分欣慰。中秋节假期完成了一项遗愿。。 每个方程看做一个节点i，将i与p_i连边即可形成一个基环森林 基环树的形态是一个链在端点上连着一个环
由于要支持修改操作，即在树上换爹的操作，所以要用LCT 因为要用LCT，所以要拆环，每个点记录virtual father表示拆环之前的father，这样，每棵基环树上有一个vfa不为null的节点，自然该点为root,将vfa称为断点。 现在要维护信息。可以发现环上的每个点转一圈都可以得到与自己的形如x≡kx+bx \equiv kx+b的线性关系。只要找出一个点的这个方程，解出来，那基环树上所有的点就都搞定了。 这样，因为断点一定在环上，而且貌似比较特殊，所以就想办法维护断点的方程。 

1
2
Access(vfa);
Splay(vfa);

这样，从vfa向上，一直到root的点就都在左子树。valup()valup()的时候就把左子树的方程带入自己得到，再把左子树带入自己的方程带入右子树的方程就行了。

TIPS

  • 同一时刻，每个节点维护的信息不需要都有什么意义，因为获得信息的时候要Access+SplayAccess+Splay。需要考虑的只是怎么样动态的得到根节点的信息，让根节点的信息有意义即可。
  • 基环树形态的特殊性使其可以用树上的结构处理。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cctype>
using std::pair;
using std::make_pair;
inline void read(int &x)
{
	char ch=0;
	int f=1;
	while(!isdigit(ch=getchar()))
		if(ch=='-') f=-1;
	x=ch-'0';
	while(isdigit(ch=getchar()))
		x=x*10+ch-'0';
	x*=f;
}
inline void read(char &ch)
{
	while(!isupper(ch=getchar()));
}
const int MAXN=30000+1;
const int P=10007;
pair<int,int> Exgcd(int a,int b)
{
	if(!b)
		return make_pair(1,0);
	else
	{
		pair<int,int> res=Exgcd(b,a%b);
		return make_pair(res.second,res.first-a/b*res.second);
	}
}
inline int Inv(int x)//MOD p相等的数字逆元相等
{
	int res=Exgcd((x+P)%P,P).first;
	return (res%P+P)%P;
}
struct Line
{
	int k,b;
	Line(int _k=1,int _b=0)
	{
		k=_k;
		b=_b;
	}
	inline int At(int pos)
	{
		return ((k*pos+b)%P+P)%P;
	}
};
inline void cat(Line& a,const Line& b)//b带入a
{
	a.b+=a.k*b.b;
	a.k*=b.k;
	a.b%=P;
	a.k%=P;
}
struct SplayNode
{
	SplayNode *son[2],*fa,*vfa;
	Line sef,suv;
	inline bool isRoot()
	{
		return fa->son[0]!=this && fa->son[1]!=this;
	}
	inline SplayNode *Root()
	{
		return fa->son[0]==fa?this:fa->Root();
	}
	inline int kind()
	{
		return fa->son[1]==this;
	}
	inline void valup()
	{
		suv=son[1]->suv;
		cat(suv,sef);
		cat(suv,son[0]->suv);
	}
}spl[MAXN],*pc=&spl[0],*T[MAXN],*null=&spl[0];
inline void trans(SplayNode *pos)
{
	SplayNode *f=pos->fa,*grf=f->fa;
	int jud=pos->kind();
	if(!f->isRoot())
		grf->son[f->kind()]=pos;
	pos->fa=grf;
	
	f->son[jud]=pos->son[!jud];pos->son[!jud]->fa=f;
	pos->son[!jud]=f;f->fa=pos;

	f->valup();
	pos->valup();
}
inline void Splay(SplayNode *pos)
{
	SplayNode *f;
	while(!pos->isRoot())
	{
		f=pos->fa;
		if(!f->isRoot())
			trans(f->kind()==pos->kind()?f:pos);
		trans(pos);
	}
}
inline void Access(SplayNode *pos)
{
	SplayNode *pred=null;
	while(pos!=null)
	{
		Splay(pos);
		pos->son[1]=pred;
		pos->valup();
		pred=pos;
		pos=pos->fa;
	}
}
void out(SplayNode *pos)
{
	if(pos==null)
		return;
	out(pos->son[0]);
	printf("%x ",pos);
	out(pos->son[1]);
}
int o(SplayNode *pos)
{
	while(!pos->isRoot())
		pos=pos->fa;
	out(pos);puts("");
}
inline SplayNode *Low(SplayNode *pos)
{
	/*while(!pos->isRoot())
		pos=pos->fa;
	*/
	Access(pos);

	Splay(pos);
	while(pos->son[0]!=null)
		pos=pos->son[0];
	return pos;
}
inline SplayNode *newnode(int k,int b)
{
	++pc;
	pc->sef=pc->suv=Line(k,b);
	pc->son[0]=pc->son[1]=pc->fa=pc->vfa=null;
	return pc;
}
int Que(int x)
{
	SplayNode *pos=T[x],*low=Low(pos),*vf=low->vfa;
	Access(vf);
	Splay(vf);
	Line f_vf=vf->suv;
	Access(pos);
	Splay(pos);
	Line f_pos=pos->suv;
	if(f_vf.b==0)
		return f_vf.k==1?-2:-1;
	else if(f_vf.k==0)
		return f_pos.At(f_vf.b);
	else
	{
		int re=-f_vf.b*Inv(f_vf.k-1);
		re=(re%P+P)%P;
		return f_pos.At(re);//144 行应该不用mod 在这里边会mod
	}
}
int Modify(int x,int k,int p,int b)
{
	SplayNode *pos=T[x];
	
	Access(pos);
	Splay(pos);

	pos->sef=Line(k,b);
	pos->valup();
	//cut
	if(pos->vfa!=null)
		pos->vfa=null;
	else
	{
		SplayNode *low=Low(pos);
		pos->son[0]->fa=null;
		pos->son[0]=null;
		pos->valup();
		if(low->Root()!=low->vfa->Root())
		{
			Access(low);
			Splay(low);
			low->fa=low->vfa,low->vfa=null;
		}
	}
	//link
	Access(pos);
	Splay(pos);
	if(pos->Root()==T[p]->Root())
		pos->vfa=T[p];
	else
		pos->fa=T[p];
}
int main()
{
	null->son[0]=null->son[1]=null;

	null->fa=null;

	//freopen("input.txt","r",stdin);
	int n;read(n);
	int t1,t2,t3,t4;
	int tf[MAXN];
	for(int i=1;i<=n;i++)
	{
		read(t1),read(tf[i]),read(t3);
		T[i]=newnode(t1,t3);
	}
	for(int i=1;i<=n;i++)
	{
		if(T[i]->Root()==T[tf[i]]->Root())
			T[i]->vfa=T[tf[i]];
		else
			T[i]->fa=T[tf[i]];
	}
	int m;read(m);
	char opt;
	for(int i=1;i<=m;i++)
	{
		read(opt);
		if(opt=='A')
		{
			read(t1);
			printf("%d\n",Que(t1));
		}
		else
		{
			read(t1),read(t2),read(t3),read(t4);
			Modify(t1,t2,t3,t4);
		}
	}

	return 0;
}

发表于 | 更新于

一个来自日照一中的蒟蒻OIer,

初三的暑假，踏上了OI的不归路。

高一，卡了个NOIp2015一等。

去省选，打了个酱油。

努力，为自己，为看好自己的人。

也放弃了许多。

神圣的事业总是痛苦的，但是，也唯有这种痛苦能把深沉给予我们。

Sometimes you have to do it alone.

NOIp2016一等

WC Ag

CTSC APIO PKUSC SDOI2017连续滚粗

D类。Fighting for PKU。希望不留下遗憾。

发表于 | 更新于

维修数列！1.5days！

Link

Solution

Splay模板题

获得区间

设区间为[l,r][l,r]，则在Splay中找到l-1和r+1的位置，将l-1Splay()Splay()到根，将r+1 到根节点的下方，则r+1的左子树即为相应的区间。即可对此区间进行相应操作。

内存回收

建立类似队列的数据结构，存储可用的数组下标。

最大子段和

//其它分治的数据结构都可以维护 对于每个节点代表的子树代表的区间[l,r][l,r]，维护从l开始向右扩展、r开始向左扩展的最大和以及该区间的最大子段和。对于每个非叶结点，求法为 lex=max(0,rson.lex,rson.sum+lson.lex)lex=max(0,rson.lex,rson.sum+lson.lex) rex=max(0,lson.rex,lson.sum+rson.rexrex=max(0,lson.rex,lson.sum+rson.rex msub=max(lson.msub,rson.msub,lson.lex+v+rson.rex)msub=max(lson.msub,rson.msub,lson.lex+v+rson.rex)

Tips

  1. 对于Reverse()Reverse()操作，每次down()down()将当前节点的rev域取反，而不是简单赋值为true
  2. 对于down()down()操作，和线段树不同，必须在执行down(pos)down(pos)时，将pos的标记下传给子节点，并把子节点的数据改对。

再做

访问的信息不能包含空节点。即使是Msub也要Split(1,TOL) 或者是在上传的时候特判 

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
using std::swap;
using std::max;
template <class T> inline T max(const T& a,const T& b,const T& c){return max(max(a,b),c);}
const int MAXN=500000+1,INF=1e9;
struct SplayNode
{
	SplayNode *son[2],*fa;
	int v,sz,
		rx,lx,msub,sumv,//lx rx必须取 
		cover,rev;
	int kind()
	{
		return fa->son[1]==this;
	}
	void same(int c)
	{
		if(!sz)
			return;
		cover=v=c;
		sumv=sz*c;
		lx=rx=msub=max(sumv,c);
	}
	void reverse()
	{
		if(!sz)
			return;
		rev^=1;
		swap(son[0],son[1]);
		swap(rx,lx);
	}
	void up()
	{
		sz=son[0]->sz+son[1]->sz+1;
		sumv=son[0]->sumv+son[1]->sumv+v;
		msub=max(son[0]->msub,
				 son[1]->msub,
				 max(0,son[0]->rx)+v+max(0,son[1]->lx));
		lx=max(son[0]->lx,
			   son[0]->sumv+v+max(0,son[1]->lx));
		rx=max(son[1]->rx,
			   son[1]->sumv+v+max(0,son[0]->rx));
	}
	void down()
	{
		if(cover!=INF)
		{
			son[0]->same(cover);
			son[1]->same(cover);
			cover=INF;
		}
		if(rev)
		{
			son[0]->reverse();
			son[1]->reverse();
			rev^=1;
		}
	}

}spl[MAXN],*null=spl,*pc=spl,*root;
void InitSplay()
{
	null->fa=null->son[0]=null->son[1]=null;
	null->sz=0;null->sumv=null->v=0;
	null->lx=null->rx=null->msub=-INF;//check this out
	null->cover=INF;null->rev=0;
}
SplayNode *S[MAXN],**top=S;
SplayNode *newSplayNode(int v)
{
	SplayNode *cur;
	if(top!=S)
		cur=*top--;
	else
		cur=++pc;
	cur->son[0]=cur->son[1]=cur->fa=null;
	cur->v=cur->rx=cur->lx=cur->msub=cur->sumv=v;
	cur->cover=INF;cur->rev=0;
	cur->sz=1;
	return cur;
}
void Rec(SplayNode *pos){*++top=pos;}
void uptoroot(SplayNode *pos)
{
	if(pos==null)
		return;
	pos->up();
	uptoroot(pos->fa);
}
SplayNode *Build(int L,int R,int *s)
{
	if(L>R)	return null;
	int MID=L+R>>1;
	SplayNode *cur=newSplayNode(s[MID]);
	cur->son[0]=Build(L,MID-1,s);cur->son[0]->fa=cur;
	cur->son[1]=Build(MID+1,R,s);cur->son[1]->fa=cur;
	cur->up();
	return cur;
}
void trans(SplayNode *pos)
{
	SplayNode *f=pos->fa,*grf=f->fa;
	int jud=pos->kind();
	if(grf!=null)//f!=root)
		grf->son[f->kind()]=pos;
	pos->fa=grf;
	pos->son[!jud]->fa=f;f->son[jud]=pos->son[!jud];
	pos->son[!jud]=f;f->fa=pos;
	f->up(),pos->up();
}
void Splay(SplayNode *pos,SplayNode *goal)
{
	SplayNode *f;
	while((f=pos->fa)!=goal)
	{
		if(f->fa!=goal)
			trans(f->kind()==pos->kind()?f:pos);
		trans(pos);
	}
	if(goal==null)
		root=pos;
}
SplayNode *Kth(int K)
{
	K++;
	SplayNode *pos=root;
	int d;
	pos=root;
	while(K)
	{
		pos->down();
		if((d=pos->son[0]->sz+1)==K)
			return pos;
		if(d<K)
		{
			K-=d;
			pos=pos->son[1];
		}
		else
			pos=pos->son[0];
	}
	return 0;
}
SplayNode *Split(int l,int r)//返回区间父节点
{
	SplayNode *pl=Kth(l-1),*pr=Kth(r+1);
	Splay(pl,null);
	Splay(pr,pl);
	return pr;
}
void Insert(int pos,int n,int *s)
{
	SplayNode *cur=Build(1,n,s),*p=Split(pos+1,pos);
	p->son[0]=cur;cur->fa=p;
	uptoroot(cur->fa);
}
void Del(SplayNode *p)
{
	if(p==null)
		return;
	Del(p->son[0]);
	Del(p->son[1]);
	Rec(p);
}
void Delete(int l,int n)
{
	int r=l+n-1;
	SplayNode *p=Split(l,r)->son[0];
	p->fa->son[p->kind()]=null;
	uptoroot(p->fa);
	Del(p);
}
void Cover(int l,int n,int c)
{
	int r=l+n-1;
	SplayNode *p=Split(l,r)->son[0];
	p->same(c);
	uptoroot(p->fa);//meixie....
}
void Reverse(int l,int n)
{
	int r=l+n-1;
	SplayNode *p=Split(l,r)->son[0];
	p->reverse();
	uptoroot(p->fa);
}
int Sum(int l,int n)
{
	int r=l+n-1;
	return Split(l,r)->son[0]->sumv;
}
int main()
{
	InitSplay();
	//freopen("input","r",stdin);
	static int s[MAXN];
	int n,m;red(n),red(m);
	for(int i=2;i<=n+1;i++)
		red(s[i]);
	//s[0]=s[n+2]=-INF;
	root=Build(1,n+2,s);
	char opt[20];
	int t1,t2,t3,t4;
	for(int i=1;i<=m;i++)
	{
		scanf("%s",opt);
		switch(opt[2])
		{
			case 'S'://ins
				red(t1),red(t2);
				for(int i=1;i<=t2;i++)
					red(s[i]);
				n+=t2;
				Insert(t1,t2,s);
				break;
			case 'L'://del
				red(t1),red(t2);
				n-=t2;
				Delete(t1,t2);
				break;
			case 'K'://msame
				red(t1),red(t2),red(t3);
				Cover(t1,t2,t3);
				break;
			case 'V'://rev
				red(t1),red(t2);
				Reverse(t1,t2);
				break;
			case 'T'://GET SUM
				red(t1),red(t2);
				printf("%d\n",Sum(t1,t2));
				break;
			case 'X':
				printf("%d\n",Split(1,n)->son[0]->msub);
				break;
		}
	}
	return 0;
}