出题人的部分笨比题解，有错轻喷
A-A Party for you started
题意：给定一颗父派子派关系树，每次询问v的权值，然后将u结点的子树权值都加x。
题解：该题是某类线段树模板题，将关系树通过dfs序/重链剖分转化成序列，在序列上用线段树维护权值区间修改以及单点查询；线段树修改、查询复杂度均为O(log(N))，所以总体复杂度O(Mlog(N))。
彩蛋：保安梗是GYQ给我看的他所崇拜的孙老师微博下的优秀评论，稍稍改编摘录如下：
我是一名保安，
每天郁郁寡欢，
上班为了下班，
每顿还要加餐；
我是一名保安，
爱吃小熊饼干，
工资只够早餐，
爱好只有看番；
我是一名保安，
混吃等死上班，
追女神的憨憨，
爱情与我无关；
我是一名保安，
保护一方平安，
我是一名保安，
明天还是保安。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define ls (o<<1)
#define rs (o<<1|1)
using namespace std;
typedef long long ll;
const int MAXN=2e4+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N,M;
int a[MAXN];
vector<int> son[MAXN];
int root;
pii ord[MAXN];
ll seg[MAXN<<2];
ll lz[MAXN<<2];
int cnt;
void dfs(int u)
{
int v;
ord[u].fi=++cnt;
for(int i=0;i<son[u].size();i++)
{
v=son[u][i];
dfs(v);
}
ord[u].se=cnt;
}
void pushdown(int o)
{
if(lz[o])
{
seg[ls]+=lz[o];
seg[rs]+=lz[o];
lz[ls]+=lz[o];
lz[rs]+=lz[o];
lz[o]=0;
}
}
void build(int o,int l,int r)
{
seg[o]=lz[o]=0;
if(l==r)
{
return ;
}
int m=l+r>>1;
build(ls,l,m);
build(rs,m+1,r);
}
void updata(int o,int l,int r,int x,int y,ll val)
{
if(x<=l&&r<=y)
{
seg[o]+=val;
lz[o]+=val;
return ;
}
int m=l+r>>1;
if(m>=x)
{
updata(ls,l,m,x,y,val);
}
if(m<y)
{
updata(rs,m+1,r,x,y,val);
}
}
ll query(int o,int l,int r,int x)
{
if(l==r)
{
return seg[o];
}
int m=l+r>>1;
pushdown(o);
if(m>=x)
{
return query(ls,l,m,x);
}
if(m<x)
{
return query(rs,m+1,r,x);
}
}
void init()
{
cnt=0;
for(int i=1;i<=N;i++)
{
son[i].clear();
}
}
void solve()
{
int u,v,x;
N=read();
M=read();
init();
for(int i=1;i<=N;i++)
{
a[i]=read();
if(!a[i])
{
root=i;
}
else
{
son[a[i]].push_back(i);
}
}
dfs(root);
build(1,1,N);
while(M--)
{
u=read();
x=read();
v=read();
write(query(1,1,N,ord[v].fi));
updata(1,1,N,ord[u].fi,ord[u].se,x);
}
}
int main()
{
solve();
return 0;
}B-Broken Pad
题意：给定两个字符串，每次将某一个位置往后的所有字符反转，或者将所有字符置0，问最小操作次数的升序操作位置。
题解：首先因为需要最小操作次数，所以不可能在同一个的位置反转两次；我们先不考虑将所有字符置0的操作，那么每次的操作不会对前面的字符有影响，因此考虑直接贪心；从前往后比较a和b，如果相同代表不需要操作，如果不同则将a的这一位以及后面的所有位反转，如此操作到结尾即可得到最小操作次数的操作序列；那么再考虑使用将所有字符置0的操作，因为不管什么情况下，动用这个操作都是将所有字符置0，所以我们只可能在最开始使用这个操作，不然相当于浪费了一些操作使得操作数不是最小操作次数，那么我们只需要比较从字符串a得到b需要的操作次数和从全0字符串得到b需要的操作次数加一的大小即可知道需不需要使用全置0操作；最后，因为字符串长1e5，每次操作是不能真的将字符都反转的，然后由于只有两种状态，所以我们只需要加一个变量标识当前位是否反转过来，就可以将复杂度简化为O(|a|)。
彩蛋：ZH是YHH（出题人）的室友，在YHH的寝室里有一个奇怪的现象，就是大部分时候YHH的运气相当好，而ZH则是另一个极端，尤其是曾经几次打扑克的时候，YHH乱摸炸弹，把ZH给炸吐了，而且YHH学过一些魔术尤其是扑克魔术，以及ZH是心理委员，所以题目背景是相当应景的=-=。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N;
char a[MAXN];
char b[MAXN];
char now[MAXN];
void init()
{
N=strlen(a+1);
}
int calc(bool reset,bool print)
{
bool head=true;
bool rev=false;
int cnt=0;
if(reset)
{
cnt++;
for(int i=1;i<=N;i++)
{
now[i]='0';
}
if(print)
{
write(0,0);
head=false;
}
}
else
{
for(int i=1;i<=N;i++)
{
now[i]=a[i];
}
}
for(int i=1;i<=N;i++)
{
if(!rev&&now[i]!=b[i]||rev&&now[i]==b[i])
{
cnt++;
if(print)
{
if(!head)
{
printf(" ");
}
head=false;
write(i,0);
}
rev^=1;
}
}
if(print)
{
printf("\n");
}
return cnt;
}
void solve()
{
scanf("%s%s",a+1,b+1);
init();
if(calc(false,false)<calc(true,false))
{
calc(false,true);
}
else
{
calc(true,true);
}
}
int main()
{
int T;
T=read();
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}C-Cook Steak
题意：烤牛排有N道工序，每道工序需要在给定的温度范围内保持1分钟，设备初始温度为0，调整1度需要1分钟，问最少几分钟完成所有工序。
题解：显然，题目要求温度调整最少，因为烤制的时间固定为N分钟；那么我们来考虑当前温度和目标温度范围的关系，如果在温度范围之内，最优的策略是使温度保持不变，否则将温度调整至临界值，也就是调整到l或者r（取决于此时温度是过低还是过高）；这样的调整策略一定是最优的，因为即使现在这个温度不是下一次需要的温度，但调整的时间是固定的，现在调整和下一次调整都是一样的；最后将调整温度需要的时间加上烤制需要的N分钟就是最终答案了；这样的处理方案是线性的，复杂度O(N)。
彩蛋：题目虽然将故事安排给了ZJH，但idea来自出题人本人的体验，因为牛肉很快熟，有一次在家里炒牛肉的时间稍微久了那么一分钟，肉就老得没法吃=-=，所以就有了这道控温的题目。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N;
char a[MAXN];
char b[MAXN];
char now[MAXN];
void init()
{
N=strlen(a+1);
}
int calc(bool reset,bool print)
{
bool head=true;
bool rev=false;
int cnt=0;
if(reset)
{
cnt++;
for(int i=1;i<=N;i++)
{
now[i]='0';
}
if(print)
{
write(0,0);
head=false;
}
}
else
{
for(int i=1;i<=N;i++)
{
now[i]=a[i];
}
}
for(int i=1;i<=N;i++)
{
if(!rev&&now[i]!=b[i]||rev&&now[i]==b[i])
{
cnt++;
if(print)
{
if(!head)
{
printf(" ");
}
head=false;
write(i,0);
}
rev^=1;
}
}
if(print)
{
printf("\n");
}
return cnt;
}
void solve()
{
scanf("%s%s",a+1,b+1);
init();
if(calc(false,false)<calc(true,false))
{
calc(false,true);
}
else
{
calc(true,true);
}
}
int main()
{
int T;
T=read();
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}D-Dessert Time
题意：有N堆蛋糕，每次拿一堆，这堆的数量不得少于对方拿的，如果不存在数量大于等于对方拿的，那么就要兜底，拿走剩下的所有蛋糕，数据保证所有数字至少出现两次。
题解：首先我们将出现的数字排序，统计出现次数，可以分类成以下三种情况：（我们只用1,2,3来代表数字大小）
①1出现奇数次，2出现偶数次，3出现偶数次；
从大到小看，第一个出现奇数次数的数字是最小的数字，如果我们第一步拿1，那么之后对手只需要按顺序拿即可让我们拿最后一个3；如果我们第一步拿2，那么对手只需模仿我们的操作，直到拿掉最后一个数字让我们兜底；因此，这是必败态；
②1出现任意次，2出现奇数次，3出现偶数次；
此时我们只要第一步拿2就是必胜，当我们拿了一个2以后，2及2以后的数字全都是偶数次，我们只需要模仿对手的操作即可拿到最后一个3使对手兜底；
③1出现偶数次，2出现偶数次，3出现偶数次；
此时我们先手取1必胜，若对手模仿我们的操作，他会拿到最后一个3，若他不模仿我们的操作而先拿一个2或者3，那么我们模仿他的操作，拿到最后一个3使对手兜底；
由于需要统计出现次数，复杂度为O(Nlog(N))。
彩蛋：最开始的题目是不保证每个数字至少出现两次的，我在写题面的样例的时候发现，如果不保证每个数字至少出现两次，那么会存在多种取法保证必胜，比如对于数据N = 4，a={1,2,2,2}，我可以先手取1使对手取最后一个2，也可以先手取2，拿到最后一个2使对手兜底，这样的话我还得写特判程序，甚至影响我的博弈策略，恶心心！因此我给数据加了保证条件。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N;
map<int,int> dic;
void init()
{
dic.clear();
}
void solve()
{
int now;
int ans;
N=read();
init();
for(int i=1;i<=N;i++)
{
now=read();
dic[now]++;
}
ans=-1;
for(auto it=(--dic.end());;--it)
{
if(it->se&1)
{
ans=it->fi;
break;
}
if(it==dic.begin())
{
break;
}
}
if(!~ans)
{
ans=dic.begin()->fi;
}
else if(ans==dic.begin()->fi)
{
ans=-1;
}
write(ans);
}
int main()
{
int T;
T=read();
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}E-Eat Grapes
题意：有一串葡萄，基础形状是长链，长链上的每个结点除了连着下一个结点以外，可能多长若干颗葡萄，而最后一个结点固定长一颗葡萄，这颗葡萄不计入数组内，两人轮流拿，只能拿正数个最后一个结点上长的葡萄，当最后一个结点上的葡萄被拿完以后，最后这个结点被视为倒数第二个结点上长的葡萄，结点数减一，即原先倒数第二个结点变成了最后一个结点。
题解：首先我们读题可以知道，我们只能一层一层地取葡萄；然后我们将数组中非0的位置定义为“局势掌控点”，因为这个结点除了连着下一个结点以外还连了至少一颗葡萄（如果是最后一个结点，由于固定的那颗葡萄不计入数组，所以它至少连着两颗葡萄），那么到了“局势掌控点”之后，该玩家可以选择一次性将这一层全拿空或是留一个让另一个玩家没得选择；既然“局势掌控点”有这样的特性，那么第一个面对“局势掌控点”的玩家可以根据从这个“局势掌控点”到下一个“局势掌控点”的距离来选择这次是拿空这一层，还是延迟一次，也就是说，第一个面对“局势掌控点”的玩家可以面对所有的“局势掌控点”，那么他就能轻松地控制好局势，令对手拿最后一颗葡萄。这个解决方案是线性的，复杂度O(N)。
彩蛋：题目要求输出的这两句话很有深意，因为吃不着才会说葡萄酸，我们分析可以得知，除了数组全0的情况，获胜者为了掌控局势，吃到的葡萄数一定是大于等于失败者的，失败者吃得少了所以就会说葡萄酸=-=。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N;
int a[MAXN];
void solve()
{
bool win;
N=read();
for(int i=1;i<=N;i++)
{
a[i]=read();
}
win=true;
for(int i=N;i>=1;i--)
{
if(a[i])
{
break;
}
if(i!=1)
{
win^=1;
}
}
printf("%s\n",win?"these are sweet grapes":"these are sour grapes");
}
int main()
{
int T;
T=read();
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}F-Flag Scramble Competition
题意：输出题面中出现最多的字母，大小写视为相同。
题解：这真的真的真的是签到题了，就算啥也不会，会写个helloworld就能做这道题，大不了咱数呗！当然，写个程序然后将题面复制过来作为输入，让程序统计出来是更快而且不会数错的！题面中出现次数最多的字母是e，输出即可。
彩蛋：英语中字母出现频率最高的就是e，胆子大点的数都不数直接输出e没毛病！我特意写了一堆废话就是为了能使这段话更偏向统计学给出的概率。下面附上两个某度上爬来的（不可靠统计）频率表：
统计近2e4个常用英文词汇：
字母 字母出现次数 字母占百分比 包含该字母的单词数 包含字母单词占百分比
e 16782 11.42% 11991 64.52%
a 12574 8.56% 10050 54.08%
i 11674 7.94% 9364 50.39%
r 11042 7.51% 9337 50.24%
t 10959 7.46% 8929 48.05%
o 10466 7.12% 8259 44.44%
n 9413 6.41% 7948 42.77%
s 8154 5.55% 6859 36.91%
l 8114 5.52% 6882 37.03%
c 6968 4.74% 6028 32.44%
u 5373 3.66% 4910 26.42%
p 4809 3.27% 4283 23.05%
m 4735 3.22% 4241 22.82%
d 4596 3.13% 4186 22.52%
h 4058 2.76% 3724 20.04%
g 3380 2.30% 3061 16.47%
b 3121 2.12% 2918 15.70%
y 2938 2.00% 2815 15.15%
f 2157 1.47% 1899 10.22%
v 1574 1.07% 1531 8.24%
w 1388 0.94% 1328 7.15%
k 1235 0.84% 1183 6.37%
x 507 0.35% 505 2.72%
z 356 0.24% 309 1.66%
q 343 0.23% 343 1.85%
j 220 0.15% 217 1.17%
由于单词也有使用频率之分：
前10个最常用的字母 频率
E 11.1607%
A 8.4966%
R 7.5809%
I 7.5448%
O 7.1635%
T 6.9509%
N 6.6544%
S 5.7351%
L 5.4893%
C 4.5388%
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
int cnt[30];
char a[MAXN];
int sa;
void init()
{
for(int i=0;i<26;i++)
{
cnt[i]=0;
}
}
void solve()
{
int now;
init();
while(~scanf("%s",a))
{
sa=strlen(a);
for(int i=0;i<sa;i++)
{
now=tolower(a[i])-'a';
if(0<=now&&now<26)
{
cnt[now]++;
}
}
}
printf("%c\n",max_element(cnt,cnt+26)-cnt+'a');
}
int main()
{
puts("e");
// solve();
return 0;
}G-Goddess
题意：给定一个N点M边的图，每个点初始值为ai，共有Q次询问，分为两种，第一种将编号为u的点赋值为x，第二种询问编号为u的点所对应的MEX{av|v与u相连}，然后将编号为u的点赋值为这个MEX。
题解：首先，对于每个顶点，MEX编号最多只能是其度数。因此，我们需要保持小于或等于其度数的值。
接下来，最多有10^5条边，因此度数大于或等于350的顶点数小于350。让我们将这些顶点称为重顶点，将其他顶点称为轻顶点。
然后，对于每个顶点，可以使用树状数组轻松计算MEX。另外对于每个顶点，MEX编号最多可以是其度数，因此我们只需创建一个大小比其度数稍大的树状数组。
对于类型1的每个查询，有两种情况。如果给定顶点是轻顶点，则遍历与该顶点直接相连的所有顶点，并修改值。如果给定顶点是重顶点，我们只更改给定顶点的值。
对于类型2的每个查询，有两种类型的顶点。
对于与给定顶点直接连接的所有轻顶点，我们已经收集了它们的值。而其他的重顶点可能未更新，但是此类顶点的数量小于350，因此我们可以遍历所有与其相连的重顶点并得到答案。
该算法的时间复杂度为O(Nlog(N)根号N)。
彩蛋：这题的彩蛋咱就不说了，懂的都懂啊，都在标题里了。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int limit=350;
const ll INF=0x3f3f3f3f;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N,M,Q;
int a[MAXN];
vector<int> es[MAXN];
vector<pii> big[MAXN];
vector<int> cnt[MAXN];
vector<int> sg[MAXN];
void init()
{
for(int i=1;i<=N;i++)
{
es[i].clear();
big[i].clear();
cnt[i].clear();
sg[i].clear();
}
}
int lowbit(int x)
{
return x&(-x);
}
void bit_updata(int i,int j,int val)
{
while(j<=es[i].size())
{
sg[i][j]+=val;
j+=lowbit(j);
}
}
int bit_query(int i,int j)
{
int res=0;
while(j)
{
res+=sg[i][j];
j-=lowbit(j);
}
return res;
}
void updata(int u,int val,int pon)
{
if(val>es[u].size())
{
return ;
}
if(pon>0)
{
if(++cnt[u][val]==1)
{
bit_updata(u,val,1);
}
}
else if(pon<0)
{
if(--cnt[u][val]==0)
{
bit_updata(u,val,-1);
}
}
}
int query(int u)
{
int l=1,r=es[u].size(),m;
while(l<=r)
{
m=l+r>>1;
if(bit_query(u,m)<m)
{
r=m-1;
}
else
{
l=m+1;
}
}
return l;
}
void solve()
{
int u,v;
int con;
int x;
N=read();
M=read();
init();
for(int i=1;i<=N;i++)
{
a[i]=read()+1;
}
for(int i=0;i<M;i++)
{
u=read();
v=read();
es[u].push_back(v);
es[v].push_back(u);
}
for(int i=1;i<=N;i++)
{
cnt[i].resize(es[i].size()+1,0);
sg[i].resize(es[i].size()+1,0);
}
for(int i=1;i<=N;i++)
{
if(es[i].size()>limit)
{
for(int j=0;j<es[i].size();j++)
{
v=es[i][j];
big[v].push_back(pii(i,INF));
}
}
else
{
for(int j=0;j<es[i].size();j++)
{
v=es[i][j];
updata(v,a[i],1);
}
}
}
Q=read();
while(Q--)
{
con=read();
if(con==1)
{
u=read();
x=read()+1;
}
else
{
u=read();
for(int i=0;i<big[u].size();i++)
{
v=big[u][i].fi;
if(a[v]!=big[u][i].se)
{
updata(u,big[u][i].se,-1);
updata(u,a[v],1);
big[u][i].se=a[v];
}
}
x=query(u);
write(x-1);
}
if(a[u]==x)
{
continue;
}
if(es[u].size()<=limit)
{
for(int j=0;j<es[u].size();j++)
{
v=es[u][j];
updata(v,a[u],-1);
updata(v,x,1);
}
}
a[u]=x;
}
}
int main()
{
solve();
return 0;
}H-Happy Time is Always Short
题意：每个人有各自的nb值，每次询问代表l到r这个区间范围内的人离开，问剩下的人中最大nb值是多少。
题解：看到区间操作就可以想到线段树，使用线段树维护区间最大值，每次更新将l，r区间的exist标记置为0，那么pushup的时候只需要比较左儿子的值乘以左儿子的exist标记和右儿子的值乘以右儿子的exist标记即可，每一次输出的答案就是seg[1]*exist[1]。
彩蛋：这道题一开始的定位是暴力，就是数据保证每个区间不相交，用map记录下每个值对应的人数，每次询问遍历l到r将这个区间内的人从map里去掉，每次的答案就是map的最后一项的key值，但是我准备出的时候发现为了能暴力保证区间不相交的数据很难出！！！为了方便起见，又考虑到其他题目已经为大家降低难度了，emmmm于是我改成可以相交用线段树做。（其实也不难对吧/doge）
然后我一开始也想过用类似双向链表的方式来标识每一个人的前一个和后一个未离开的人，这样维护起来类似并查集路径压缩，每个人也只会被遍历常数次，实现起来有点麻烦不过也可以做。
#include<bits/stdc++.h>
#define ls (o<<1)
#define rs (o<<1|1)
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
inline ll read()
{
ll x=0,f=1;
char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
inline void write(ll x,char con='\n')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10,0);
putchar(x%10+'0');
if(con)
{
printf("%c",con);
}
}
ll N,M;
ll nb[MAXN];
ll seg[MAXN<<2];
bool exist[MAXN<<2];
void pushup(int o)
{
seg[o]=max(seg[ls]*exist[ls],seg[rs]*exist[rs]);
}
void build(int o,int l,int r)
{
exist[o]=true;
if(l==r)
{
seg[o]=nb[l];
return ;
}
int m=l+r>>1;
build(ls,l,m);
build(rs,m+1,r);
pushup(o);
}
void updata(int o,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
exist[o]=false;
return ;
}
int m=l+r>>1;
if(x<=m&&exist[ls])
{
updata(ls,l,m,x,y);
}
if(m<y&&exist[rs])
{
updata(rs,m+1,r,x,y);
}
pushup(o);
}
void init()
{
build(1,1,N);
}
void solve()
{
int l,r;
N=read();
M=read();
for(int i=1;i<=N;i++)
{
nb[i]=read();
}
init();
while(M--)
{
l=read();
r=read();
updata(1,1,N,l,r);
write(seg[1]*exist[1]);
}
}
int main()
{
int T;
T=read();
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}
京公网安备 11010502036488号