题解 P6881 【[JOI 2020 Final] 火事】
xtx1092515503
2020-12-03 10:08:39
数据结构好题。
------------
我们考虑画出每一时刻所有位置的值：
这其中，我们可以找到最标准的情形：里面的元素 $\color{cyan}{7}$。可以看到，随着时间增加，它呈现一个平行四边形。
那么这个平行四边形由上面构成呢？我们考虑用单调栈找出每个位置向左向右第一个比它大的位置 $l_i,r_i$。则我们会发现，平行四边形的四个顶点是 $(i,0),(r_i-1,r_i-i-1),(r_i-1,r_i-l_i-2),(i,i-l_i-1)$。
我们考虑此时的询问，在坐标系上，就成为了一段水平线段。考虑差分一下，就变成了两条沿 $x$ 轴负方向的的射线。
考虑把一个平行四边形拆成三个三角形：
如图，绿色平行四边形=大三角形-蓝三角形-紫三角形。
然后我们发现，每个三角形的形状都是一样的，并且都有一条腰在 $x$ 轴上。故我们可以用其上方顶点来唯一确定一个三角形。则有大三角形顶点 $(r_i-1,r_i-l_i-2)$，蓝三角形顶点 $(i-1,i-l_i-2)$，紫三角形顶点 $(r_i-1,r_i-i-2)$。
我们考虑一条沿 $x$ 轴负方向的射线与三角形的交线段长度：
如图，如果该射线是绿线（原点在三角形内），可以将其平移至紫线位置，然后就可以拆括号计算了。如果该直线是棕线，则也可以简单计算。
于是我们可以用扫描线维护对于递增的射线原点的 $x$ 坐标，相应的位于其左侧的三角形们和位于其右侧的三角形们，然后分别转移即可。
至于如何转移，可以各通过两棵树状数组，一棵维护系数和，一棵维护带权坐标和，然后分别转移即可。共需四棵树状数组。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[200100],l[200100],r[200100],stk[200100],tp,lim,mil;
ll res[200100];
namespace BIT1{//a BIT for triangular summary.
ll t1[600100],t2[600100];//t1 for weighted sum, t2 for common sum.
void ADD(int x,int y){
x--;
ll tmp=1ll*y*x;
for(int i=x+n+1;i<=3*n;i+=i&-i)t1[i]+=tmp,t2[i]+=y;
}
ll SUM(int x){
ll ret=0;
for(int i=x+n+1;i;i-=i&-i)ret-=t1[i],ret+=t2[i]*x;
return ret;
}
}
namespace BIT2{
ll t1[600100],t2[600100];
void ADD(int x,int y){
x++;
ll tmp=1ll*y*x;
for(int i=x+n+1;i;i-=i&-i)t1[i]+=tmp,t2[i]+=y;
}
ll SUM(int x){
ll ret=0;
for(int i=x+n+1;i<=3*n;i+=i&-i)ret+=t1[i],ret-=t2[i]*x;
return ret;
}
}
void ADD1(int x,int y,int z){BIT1::ADD(x-y,z);}
void ADD2(int x,int y,int z){BIT2::ADD(y,z);}
struct Query{
int x,y,id;
Query(int u=0,int v=0,int w=0){x=u,y=v,id=w;}
friend bool operator <(const Query &x,const Query &y){return x.x<y.x;}
}q[400100];
struct Tri{
int x,y,a;
Tri(int u=0,int v=0,int w=0){x=u,y=v,a=w;}
friend bool operator <(const Tri &x,const Tri &y){return x.x<y.x;}
}p[800100];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
while(tp&&a[i]>a[stk[tp]])l[stk[tp--]]=i;
stk[++tp]=i;
}
while(tp)l[stk[tp]]=stk[tp]-n-1,tp--;
for(int i=1;i<=n;i++){
while(tp&&a[stk[tp]]<=a[i])r[stk[tp--]]=i;
stk[++tp]=i;
}
while(tp)r[stk[tp--]]=n+1;
for(int i=1;i<=n;i++){
p[++lim]=Tri(i-1,i-l[i]-2,-a[i]);
p[++lim]=Tri(r[i]-1,r[i]-l[i]-2,a[i]);
p[++lim]=Tri(r[i]-1,r[i]-i-2,-a[i]);
}
for(int i=1;i<=lim;i++)ADD1(p[i].x,p[i].y,p[i].a);
sort(p+1,p+lim+1);
for(int i=1,t,l,r;i<=m;i++){
scanf("%d%d%d",&t,&l,&r);
q[++mil]=Query(l-1,t,-i);
q[++mil]=Query(r,t,i);
}
sort(q+1,q+mil+1);
for(int i=1,j=1;i<=mil;i++){
while(j<=lim&&p[j].x<q[i].x)ADD1(p[j].x,p[j].y,-p[j].a),ADD2(p[j].x,p[j].y,p[j].a),j++;
int lambda=(q[i].id>0?1:-1);q[i].id=abs(q[i].id);
res[q[i].id]+=(BIT1::SUM(q[i].x-q[i].y)+BIT2::SUM(q[i].y))*lambda;
}
for(int i=1;i<=m;i++)printf("%lld\n",res[i]);
// for(int i=1;i<=n;i++)printf("%d %d\n",l[i],r[i]);
return 0;
}
```