「AHOI / HNOI2017」影魔

「AHOI / HNOI2017」影魔

cdq 分治写法。

首先利用单调栈求出 \(L_i,R_i\) 分别表示在 \(i\) 左边第一个 \(K\) 值大于 \(K_i\)，右边第一个 \(K\) 值大于 \(K_i\) 的位置。

如 \(L_i\) 不存在设为 0，如 \(R_i\) 不存在设为 \(n+1\)。

然后我们考虑提供 \(p1\) 攻击力的情况：

容易发现对于一个点 \(i\)，以及一个询问 \(l,r\)。如果 \(l,r\) 同时包含 \(L_i,i\) 那么 \(i\) 会对询问产生 \(p1\) 的贡献。如果 \(l,r\) 同时包含 \(i,R_i\)，那么 \(i\) 会对询问产生 \(p1\) 的贡献。

形式化的说，也就是 \(l\le L_i\le i\le r\) 的时候会产生贡献，\(l\le i\le R_i\le r\) 的时候会产生贡献。那么这是个二维偏序问题，可以用 cdq 分治来解决。具体实现是将询问看成点，\(l,r\) 看做权值，并将每个 \(i\) 拆成两个点，权值分别为 \(L_i,i\) 和 \(i,R_i\)。

然后我们考虑提供 \(p2\) 攻击力的情况：

对于一个点 \(i\)，我们考虑其为 \(c\) 的情况。容易发现对于一个询问 \(l,r\)。当 \(l,r\) 包含 \(L_i,i,R_i\) 时，那么它对询问会产生 \((R_i-L_i-2)\times p2\) 的贡献。

当 \(l,r\) 仅包含 \(L_i,i\) 时，他会对询问产生 \((r-i)*p2\) 的贡献。

当 \(l,r\) 仅包含 \(i,R_i\) 时，他会对询问产生 \((i-l)*p2\) 的贡献。

抽象成表达式就是 \(l\le L_i< i< R_i\le r\) ，\(l\le L_i，\(L_i。这三种情况，易发现这个是个三维偏序。可以用 cdq 分治来处理。处理方法同上，将询问看成点，并赋予三个权值。

实现起来有较多细节包括但不限于：

1. 如果权值相等将询问放在前面。
2. 排序解决的那一维可能会包含相等的情况，而双指针处理的部分不会包含相等的情况，所以只能用双指针或树状数组处理 \(<\) 号，因此得多 cdq 几次。

由于 \(n,m\) 同阶。因此时间复杂度为 \(O(n\log^2 n)\) 。外加大常数，请开 O2。

代码如下：

#include
#define ll long long
#define lowbit(i) (i&(-i))
using namespace std;
const int MAXN = 2e5+5;
bool Small;
int n,m,p1,p2,A[MAXN];
int st[MAXN],top,L[MAXN],R[MAXN],le[MAXN],ri[MAXN];
bool Sunny;
struct BIT
{
	int t[MAXN];
	void add(int pos,int x)
	{
		for(int i=pos;i<=n;i+=lowbit(i)) t[i]+=x;
	}
	ll que(int pos)
	{
		ll ans=0;
		for(int i=pos;i;i-=lowbit(i)) ans+=t[i];
		return ans;
	}
}v,cnt;
struct node
{
	int l,r,id,v;
}Q[MAXN<<2];
bool cmp1(node x,node y){return x.l==y.l?x.id>y.id:x.l>y.l;}
bool cmp2(node x,node y){return x.r==y.r?x.id>y.id:x.ry.id:x.ly.id:x.vy.id:x.r>y.r;}
ll Ans[MAXN];
void solve1(int l,int r)
{
	if(l==r) return ;
	int mid=l+r>>1;
	solve1(l,mid);solve1(mid+1,r);
	sort(Q+l,Q+mid+1,cmp2);sort(Q+mid+1,Q+r+1,cmp2);
	int cur=mid+1;ll cnt=0;
	for(int i=l;i<=mid;++i)
	{
		while(Q[cur].r<=Q[i].r&&cur<=r) cnt+=(Q[cur].id==0),++cur;
		if(Q[i].id!=0) Ans[Q[i].id]+=cnt*p1;
	}
}
void solve2(int l,int r)
{
	if(l==r) return ;
	int mid=l+r>>1;
	solve2(l,mid);solve2(mid+1,r);
	sort(Q+l,Q+mid+1,cmp2);sort(Q+mid+1,Q+r+1,cmp2);
	int cur=mid+1;ll tmp=0;
	for(int i=l;i<=mid;++i)
	{
		while(Q[cur].r<=Q[i].r&&cur<=r)
		{
			if(Q[cur].id==0) tmp+=Q[cur].r-Q[cur].l-2;
			++cur;
		}
		if(Q[i].id!=0) Ans[Q[i].id]+=tmp*p2;
	}
	cur=r;
	for(int i=mid;i>=l;--i)
	{
		while(cur>=mid+1&&Q[cur].r>Q[i].r)
		{
			if(Q[cur].id==0)
			{
				v.add(Q[cur].v,Q[cur].v);
				cnt.add(Q[cur].v,1);
			}
			--cur;
		}
		if(Q[i].id!=0)
		{
			ll val=v.que(Q[i].r),c=cnt.que(Q[i].r);
			Ans[Q[i].id]+=(c*Q[i].r-val)*p2;
		}
	}
	for(int i=r;i>cur;--i)
	{
		if(Q[i].id==0)
		{
			v.add(Q[i].v,-Q[i].v);
			cnt.add(Q[i].v,-1);
		}
	}
}
void solve3(int l,int r)
{
	if(l==r) return ;
	int mid=l+r>>1;
	solve3(l,mid);solve3(mid+1,r);
	sort(Q+l,Q+mid+1,cmp3);sort(Q+mid+1,Q+r+1,cmp3);
	int cur=mid+1;
	for(int i=l;i<=mid;++i)
	{
		while(cur<=r&&Q[cur].l