今天的题依旧很难。
然而对于机房里某些大佬来说依旧很简单。
但是我不是大佬。
线段树
T1
其实这题很简单，我都会写，但是赛时写炸了（
其大致思路是维护每个区间是否有雾。对于每个查询，先判断点x是否有雾，再判断区间 [1,x] 或区间 [x,s] 是否没有雾（即题面中两个特殊情况）。对于其他情况二分查找 x 左右没有雾的区间即可。
code:
#include
using namespace std;
const int S=1e6;
int s,q,tr[S],tag[S];
void downtag(int i,int l,int r){
if (tag[i]==-1){
return;
}
int mid=(l+r)>>1;
tag[i*2]=tag[i];
tag[i*2+1]=tag[i];
tr[i*2]=tag[i];
tr[i*2+1]=tag[i];
tag[i]=-1;
return;
}
void ch(int i,int l,int r,int x,int y,int v){
if (x=r){
tag[i]=v;
tr[i]=v;
return;
}
downtag(i,l,r);
int mid=(l+r)>>1;
if (x<=mid){
ch(i*2,l,mid,x,y,v);
}
if (mid<y){
ch(i*2+1,mid+1,r,x,y,v);
}
tr[i]=(tr[i*2]||tr[i*2+1]);
return;
}
int qr(int i,int l,int r,int x,int y){
if (x=r){
return tr[i];
}
downtag(i,l,r);
int mid=(l+r)>>1;
int ret=0;
if (x<=mid){
ret=(ret||qr(i*2,l,mid,x,y));
}
if (mid<y){
ret=(ret||qr(i*2+1,mid+1,r,x,y));
}
return ret;
}
int main()
{
freopen("explore.in","r",stdin);
freopen("explore.out","w",stdout);
memset(tag,-1,sizeof tag);
scanf("%d%d",&s,&q);
while (q--){
int opt;
scanf("%d",&opt);
if (opt==1){
int l,r;
scanf("%d%d",&l,&r);
ch(1,1,s,l,r,1);
}
else if (opt==2){
int l,r;
scanf("%d%d",&l,&r);
ch(1,1,s,l,r,0);
}
else if (opt==3){
int x,ansl,ansr;
scanf("%d",&x);
if (qr(1,1,s,x,x)){
printf("0\n");
continue;
}
if ((!qr(1,1,s,1,x))||(!qr(1,1,s,x,s))){
printf("INF\n");
continue;
}
int l=1,r=x;
while (l>1;
if (qr(1,1,s,mid,x)){
l=mid+1;
}
else{
r=mid;
}
}
ansl=l;
l=x,r=s;
while (l>1;
if (qr(1,1,s,x,mid)){
r=mid-1;
}
else{
l=mid;
}
}
ansr=l;
printf("%d\n",ansr-ansl+1);
}
}
return 0;
}
T2
代码在调。
显然最优解应该取排序后相邻的三个数。
考虑最劣情况，是排序后像一个斐波那契数列那样，因此根据 a_i 的范围很容易得出只需要维护排序后的最大的50个数即可。
code（未调完，没AC）：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,a[N];
struct node{
int maxx[50];
}tr[N<<2];
void upd(int i,int l,int r){
int mid=(l+r)>>1;
int nn=min(r-l+1,45),nl=min(mid-l+1,45),nr=min(r-mid,45);
int cnt=1,cntl=1,cntr=1;
while (cnt<=nn&&cntl<=nl&&cntr<=nr){
if (tr[i<<1].maxx[cntl]>=tr[(i<<1)+1].maxx[cntr]){
tr[i].maxx[cnt++]=tr[i<<1].maxx[cntl++];
}
else{
tr[i].maxx[cnt++]=tr[(i<<1)+1].maxx[cntr++];
}
}
while (cnt<=nn&&cntl<=nl){
tr[i].maxx[cnt++]=tr[i<<1].maxx[cntl++];
}
while (cnt<=nn&&cntr<=nr){
tr[i].maxx[cnt++]=tr[(i<<1)+1].maxx[cntr++];
}
return;
}
void build(int i,int l,int r){
if (l==r){
tr[i].maxx[1]=a[l];
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build((i<<1)+1,mid+1,r);
upd(i,l,r);
return;
}
void change(int i,int l,int r,int x,int v){
if (l==r){
tr[i].maxx[1]=v;
return;
}
int mid=(l+r)>>1;
if (x<=mid){
change(i<<1,l,mid,x,v);
}
else{
change((i<<1)+1,mid+1,r,x,v);
}
upd(i,l,r);
return;
}
node query(int i,int l,int r,int x,int y){
if (x<=l&&y>=r){
return tr[i];
}
int mid=(l+r)>>1;
node ret,retl,retr;
memset(ret.maxx,0,sizeof ret.maxx);
if (x<=mid){
retl=query(i<<1,l,mid,x,y);
}
if (y>=mid+1){
retr=query((i<<1)+1,mid+1,r,x,y);
}
int nn=min(r-l+1,45),nl=min(mid-l+1,45),nr=min(r-mid,45);
int cnt=1,cntl=1,cntr=1;
while (cnt<=nn&&cntl<=nl&&cntr<=nr){
if (retl.maxx[cntl]>=retr.maxx[cntr]){
ret.maxx[cnt++]=retl.maxx[cntl++];
}
else{
ret.maxx[cnt++]=retr.maxx[cntr++];
}
}
while (cnt<=nn&&cntl<=nl){
ret.maxx[cnt++]=retl.maxx[cntl++];
}
while (cnt<=nn&&cntr<=nr){
ret.maxx[cnt++]=retr.maxx[cntr++];
}
return ret;
}
int main()
{
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while (q--){
int opt;
scanf("%d",&opt);
if (opt==1){
int pos,val;
scanf("%d%d",&pos,&val);
change(1,1,n,pos,val);
}
else{
int l,r;
scanf("%d%d",&l,&r);
l=max(1,l);
r=min(n,r);
node m=query(1,1,n,l,r);
int nn=min(r-l+1,45),ans=0;
for (int i=1;i<=nn-2;i++){
if (m.maxx[i+2]+m.maxx[i+1]>m.maxx[i]&&m.maxx[i]-m.maxx[i+1]>m.maxx[i+2]){
ans=m.maxx[i+2]+m.maxx[i+1]+m.maxx[i];
break;
}
}
printf("%d\n",ans);
}
}
return 0;
}
T3
感觉有点复杂，明天再看看。
LCA和倍增
去你谷搜了一下发现都是紫起步，并且带有大量在我知识盲区中的算法，因此先放在这里。