[loj3256]火灾

将问题差分，即求$\sum_{i=1}^{r}S_{i}(t)-\sum_{i=1}^{l-1}S_{i}(t)$，由于两者类似，不妨考虑前者

构造矩阵$A_{i,j}=S_{j}(i)-S_{j}(i-1)$，记初始的序列为$a_{i}$，则$S_{i}(t)=a_{i}+\sum_{j=1}^{t}A_{j,i}$

将之代入，即求$\sum_{i=1}^{r}(a_{i}+\sum_{j=1}^{t}A_{j,i})$，前者直接前缀和即可，下面考虑后者，即求矩阵$A$

对于每一个$i$，求出所有$S_{j}(i-1)=a_{i}$且$S_{j}(i)\ne a_{i}$的$A_{i,j}$，显然即包括了所有位置

具体的，这些位置形式如下：令$x=\max_{x\le i,a_{x}>a_{i}}x$（若不存在则跳过）和$y=\min_{y>i,a_{y}\ge a_{i}}y$（若不存在则为$n+1$），即$\forall i\le j<y,A_{j-x,j}=a_{x}-a_{i}$

这个用数据结构不易维护，但我们可以考虑其对某一次询问的贡献，即$(a_{x}-a_{i})\sum_{i\le j<y,j-x\le t,j\le r}1$，关于后者再简单处理即$(a_{x}-a_{i})\max(\min(y-1,t+x,r)-i+1,0)$

下面，对$\min(y-1,t+x,r)$的值分类讨论：

1.$y-1$为最小值，即$t\ge y-x$且$r\ge y$

2.$t+x$为最小值，即$i-x\le t\le y-x-1$且$r-t\ge x$

3.$r$为最小值，即$i\le r\le y-1$且$r-t\le x-1$

得出上述结果时，注意：

1.最小值还需要满足$\ge i$，否则显然贡献为0，不需要考虑

2.注意等号和不等号，使得在相等时最小值仍被唯一确定

对每一种情况分别处理（后相加），将其中后者的限制通过排序解决，前者在排序后用线段树维护即可

时间复杂度为$o(n\log n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define ll long long

 5 #define pll pair<ll,ll>

 6 #define mp make_pair

 7 #define fi first

 8 #define se second

 9 #define L (k<<1)

10 #define R (L+1)

11 #define mid (l+r>>1)

12 struct Data{

13     int p,i,x,y;

14     int get(){

15         if (!p)return x;

16         return y-x;

17     }

18 };

19 vector<Data>v;

20 int n,m,t,l,r,st[N],ls[N],rs[N];

21 ll a[N],sum[N],ans[N];

22 pll f[N<<2];

23 bool cmp1(Data x,Data y){

24     return (x.y<y.y)||(x.y==y.y)&&(abs(x.p)<abs(y.p));

25 }

26 bool cmp2(Data x,Data y){

27     return (x.get()<y.get())||(x.get()==y.get())&&(abs(x.p)<abs(y.p));

28 }

29 pll merge(pll x,pll y){

30     return mp(x.fi+y.fi,x.se+y.se);

31 }

32 void update(int k,int l,int r,int x,int y,pll z){

33     if ((l>y)||(x>r))return;

34     if ((x<=l)&&(r<=y)){

35         f[k]=merge(f[k],z);

36         return;

37     }

38     update(L,l,mid,x,y,z);

39     update(R,mid+1,r,x,y,z);

40 }

41 ll query(int k,int l,int r,int x){

42     ll ans=f[k].fi+x*f[k].se;

43     if (l==r)return ans;

44     if (x<=mid)return ans+query(L,l,mid,x);

45     return ans+query(R,mid+1,r,x);

46 }

47 int main(){

48     scanf("%d%d",&n,&m);

49     for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

50     for(int i=1;i<=n;i++){

51         while ((st[0])&&(a[i]>=a[st[st[0]]]))st[0]--;

52         if (st[0])ls[i]=st[st[0]];

53         st[++st[0]]=i;

54     }

55     st[0]=0;

56     for(int i=n;i;i--){

57         while ((st[0])&&(a[i]>a[st[st[0]]]))st[0]--;

58         if (st[0])rs[i]=st[st[0]];

59         st[++st[0]]=i;

60     }

61     for(int i=1;i<=n;i++){

62         if (ls[i]){

63             if (!rs[i])rs[i]=n+1;

64             v.push_back(Data{0,i,ls[i],rs[i]});

65         }

66     }

67     for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];

68     for(int i=1;i<=m;i++){

69         scanf("%d%d%d",&t,&l,&r);

70         ans[i]=sum[r]-sum[l-1];

71         v.push_back(Data{1,i,t,r});

72         if (l>1)v.push_back(Data{-1,i,t,l-1});

73     }

74     sort(v.begin(),v.end(),cmp1);

75     for(int i=0;i<v.size();i++){

76         if (v[i].p)ans[v[i].i]+=v[i].p*query(1,1,n,v[i].x);

77         else update(1,1,n,v[i].y-v[i].x,n,mp((a[v[i].x]-a[v[i].i])*(v[i].y-v[i].i),0));

78     }

79     sort(v.begin(),v.end(),cmp2);

80     memset(f,0,sizeof(f));

81     for(int i=0;i<v.size();i++){

82         if (v[i].p)ans[v[i].i]+=v[i].p*query(1,1,n,v[i].x);

83         else update(1,1,n,v[i].i-v[i].x,v[i].y-v[i].x-1,mp((a[v[i].x]-a[v[i].i])*(v[i].x-v[i].i+1),a[v[i].x]-a[v[i].i]));

84     }

85     memset(f,0,sizeof(f));

86     for(int i=(int)v.size()-1;i>=0;i--){

87         if (v[i].p)ans[v[i].i]+=v[i].p*query(1,1,n,v[i].y);

88         else update(1,1,n,v[i].i,v[i].y-1,mp((a[v[i].x]-a[v[i].i])*(1-v[i].i),a[v[i].x]-a[v[i].i]));

89     }

90     for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);

91 }

巴特西

[loj3256]火灾

最新文章

热门文章