P8037 [COCI2015-2016#7] Prokletnik

思绪：

起首考虑离线。
设 \(Min-nxt_i\) 表示下一个小于 \(a_i\) 处的位置，\(Max-nxt_i\) 表示下一个大于 \(a_i\) 处的位置。
那么 \([l,r]\) 是邪术区间当且仅当：

• \(r\) 是 \([l,r]\) 的最大值，且 \(r < Min - nxt_l\)。
  
• \(r\) 是 \([l,r]\) 的最小值，且 \(r < Max - nxt_l\)。
  

再令 \(Min-pre_i\) 表示上一个小于 \(a_i\) 处的位置，\(Max-pre_i\) 表示上一个大于 \(a_i\) 处的位置。
那么我们可以对于每个 \(r\)，求出对应的 \(l\) 的氛围：

• 若 \(r\) 是 \([l,r]\) 的最大值，则 \(l \in [Max-pre_r+1,r]\)。
  
• 若 \(r\) 是 \([l,r]\) 的最小值，则 \(l \in [Min-pre_r+1,r]\)。
  

则可以在扫描线扫到 \(r\) 时，对上述两个区间更新答案；留意到对于 \(l\) 的答案是 \(r-l+1\)，那么对于区间 \([a,b]\)，其的右端点若都是 \(r\)，要使得贡献最大，应该选择 \([a,r]\) 区间，但是有些点是无法对 \(r\) 造成贡献的（对于这类点的处理见下文），于是我们需要找到 \([a,b]\) 内最小的能对 \(r\) 造成贡献的点，维护一个 set 二分即可，需要支持删除。

但是我们需要满足 \(r < Min-nxt_l\) 或 \(r=mod)?(x+y-mod)x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef int ll;bool Begin;const ll N=5e5+10;inline ll read(){    ll x=0,f=1;    char c=getchar();    while(c'9'){        if(c=='-')          f=-1;        c=getchar();    }    while(c>='0'&&c

继续阅读请点击广告