显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef multiset<int>::iterator ITER;
const int SIZEN=100010;
const int INF=0x7fffffff/2;
void printset(multiset<int> s){
for(ITER key=s.begin();key!=s.end();key++){cout<<(*key)<<" ";}cout<<endl;
}
int log2(int x){
int ans=-1;
while(x){ans++;x>>=1;}
if(ans<0) ans=0;
return ans;
}
int ST[20][SIZEN];
void build_st(int a[],int n){
int m=log2(n);
for(int i=0;i<n;i++) ST[0][i]=i;
for(int j=1;j<=m;j++){
for(int i=0;i<n;i++){
if(i+(1<<j)-1<n){
int p=ST[j-1][i],q=ST[j-1][i+(1<<(j-1))];
ST[j][i]=(a[p]>a[q]?p:q);
}
}
}
}
int RMQ(int a[],int l,int r){
int m=log2(r-l+1);
int p=ST[m][l],q=ST[m][r-(1<<m)+1];
return a[p]>a[q]?p:q;
}
int N;
int H[SIZEN];
multiset<int> SL[SIZEN],SH[SIZEN];
int calc(multiset<int> &sl,multiset<int> &sh,int high){//l:0,h:1
ITER key1=sl.begin(),key2=sh.begin();
int now=sl.size(),ans=now;
for(;key1!=sl.end()&&(*key1)<=high;key1++){
while(key2!=sh.end()&&(*key1)>=(*key2)) now++,key2++;
ans=max(ans,now);
now--;
}
key1=sl.begin(),key2=sh.begin();
now=sl.size();
for(;key2!=sh.end()&&(*key2)<=high;key2++){
now++;
while(key1!=sl.end()&&(*key2)>(*key1)) now--,key1++;
ans=max(ans,now);
}
return ans;
}
int merge(int a,int b,int lim,int &cnt){
if(SL[a].size()+SH[a].size()>SL[b].size()+SH[b].size()) swap(a,b);
for(ITER key=SL[a].begin();key!=SL[a].end();key++){
if((*key)>lim) SL[b].insert(*key);
}
for(ITER key=SH[a].begin();key!=SH[a].end();key++){
if((*key)>lim) SH[b].insert(*key);
else cnt++;
}
for(ITER key=SL[b].begin();key!=SL[b].end();){
ITER key1=key;key1++;
if((*key)<=lim){
SL[b].erase(key);
key=key1;
}
else break;
}
for(ITER key=SH[b].begin();key!=SH[b].end();){
if((*key)<=lim){
ITER key1=key;key1++;
SH[b].erase(key);
key=key1;
cnt++;
}
else break;
}
return b;
}
int DQ(int a,int b,int mx,int &s,int &cnt){
if(a==b){
cnt=0;
s=a;
return calc(SL[a],SH[a],mx);
}
int p=RMQ(H,a,b-1);
int ans=0;
int s1,s2,cnt1,cnt2;
ans=DQ(a,p,H[p],s1,cnt1)+DQ(p+1,b,H[p],s2,cnt2);
cnt=cnt1+cnt2;
s=merge(s1,s2,H[p],cnt);
ans=max(ans,calc(SL[s],SH[s],mx)+cnt);
return ans;
}
void read(void){
int Q;
scanf("%d%d",&N,&Q);
for(int i=1;i<N;i++) scanf("%d",&H[i]);
H[0]=H[N]=INF;
for(int i=1;i<=N;i++) SL[i].clear(),SH[i].clear();
build_st(H,N+1);
int x,y,z;
for(int i=1;i<=Q;i++){
scanf("%d%d%d",&x,&y,&z);
if(z==0){
SL[x].insert(y);
}
else{
SH[x].insert(y+1);
}
}
}
int main(){
//freopen("input.in","r",stdin);
//freopen("C:/Users/Admin/Codes/OI/DATA/duipai/input.in","r",stdin);
freopen("discoverwatertank.in","r",stdin);
freopen("discoverwatertank.out","w",stdout);
int T;scanf("%d",&T);
int s,cnt,kase=0;
while(T--){
read();
printf("Case #%d: %d\n",++kase,DQ(1,N,INF,s,cnt));
}
return 0;
}
cstdio