在乏善可陈的世界里，你熠熠生辉。
探险
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
小林想去森林探险。森林中有一条长度为S的小路：
若位置x有浓雾，则位置x的视野为0；
若从x一直到S或从1一直到x都没有浓雾，则视野为 INF；
其他情况下，位置x的视野定义为max(R-L+1)，其中L≤x≤R,∀y∈[L,R],位置y没有浓雾。
具体来说，会有以下事件发生：
1 L R ：位置[L,R]产生浓雾；
2 L R ：位置[L,R]浓雾消散；
3 x ：询问位置x的视野。
一开始，小路上没有任何浓雾。
输入
第一行包含一个整数S。
第二行包含一个整数Q，表示事件总数。
接下来Q行，每行描述一个事件。
输出
对于每个询问事件，输出一行一个整数或字符串”INF”（不含引号）。
样例输入 Copy
5
5
1 2 4
3 1
3 4
2 3 3
3 3
样例输出 Copy
INF
0
1
提示
对于40%的数据，S×Q≤5×10^7。
对于100%的数据，2≤S≤10^5 ， 2≤Q≤ 2×10^5，1≤L≤R≤S，1≤x≤S。
思路：
区间修改果断线段树。
这个题查询的地方很巧妙，定义的最大视野是分别向左向右到达的没有浓雾的最远距离。
假设这一点有浓雾，那就输出0；如果没有浓雾，那么在分别向左向右延伸的一段区间肯定也没有浓雾；综上，可以二分分别查找左右的最大边界。
具体细节见代码吧~
代码：
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> PII; #define I_int ll #define PI 3.1415926535898 inline ll read() { ll x=0,f=1;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();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); puts(""); } const int maxn=1e6+7; int n,m; int v,l,r; struct node{ int l,r;///左右边界 int lazy;///懒标记 int st;//0表示没有浓雾，1表示有浓雾 }a[maxn*4]; void pushup(int u){ a[u].st=a[u<<1].st|a[u<<1|1].st;//当两个子节点都没都浓雾时才没有浓雾 } void pushdown(int u){ auto &root=a[u],&left=a[u<<1],&right=a[u<<1|1]; if(root.lazy!=-1){ left.lazy=right.lazy=left.st=right.st=root.lazy; root.lazy=-1; } } void build(int u,int l,int r){ a[u].l=l,a[u].r=r; if(l==r){ a[u].lazy=a[u].st=0;///初始都没有浓雾 } else{ int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } } void update(int u,int l,int r,int ll,int rr,int v){ if(l>r||r<ll||l>rr) return ;///完全不包含 if(l>=ll&&r<=rr){//完全包含 a[u].st=v; a[u].lazy=v; } else{ int mid=(l+r)>>1; pushdown(u);//传递懒惰标记 update(u<<1,l,mid,ll,rr,v);//更新左右子树 update(u<<1|1,mid+1,r,ll,rr,v); pushup(u); } } int query(int u,int l,int r,int ll,int rr){ if(l>r||r<ll||l>rr) return 0;///完全不包含 if(l>=ll&&r<=rr) return a[u].st;///完全包含 int mid=(l+r)>>1; pushdown(u);//传递懒惰标记 int resl=query(u<<1,l,mid,ll,rr),resr=query(u<<1|1,mid+1,r,ll,rr); if(rr<=mid) return resl;///完全在左子树 if(ll>mid) return resr;//完全在右子树 return (resl|resr); } void solve(int x){ int xx=query(1,1,n,x,x); if(xx){//x处有浓雾 puts("0"); return ; } int lx=query(1,1,n,1,x);//从1-x一直没有浓雾 if(lx==0){ puts("INF"); return ; } int rx=query(1,1,n,x,n); if(rx==0){ puts("INF"); return ; } int l=1,r=x,resl=x; ///在1-x内 二分找左边的最远视野 while(l<=r){ int mid=(l+r)>>1; if(query(1,1,n,mid,x)==0){//mid-x一直没浓雾 resl=mid,r=mid-1;//继续往左找左边界 } else l=mid+1; } l=x,r=n;int resr=x; while(l<=r){ int mid=(l+r)>>1; if(query(1,1,n,x,mid)==0){//x-mid没有浓雾，继续向右寻找右边界 resr=mid,l=mid+1; } else r=mid-1; } out(resr-resl+1); // cout<<<<endl; } int main(){ n=read();m=read(); build(1,1,n); while(m--){ v=read(); if(v==1){ l=read();r=read(); update(1,1,n,l,r,1);///产生浓雾 } else if(v==2){ l=read();r=read(); update(1,1,n,l,r,0);///消散浓雾 } else{ int x;x=read();///查询视野 solve(x); } } return 0; }
感觉就是个板子题但是写了一个多小时。。
看网上还有用珂朵莉树过的，真·奇奇怪怪的数据结构：传送门
