Wuyanru's blog
0%

[NOIP2022] 比赛

发表于 分类于 ，

被数据结构爆啦！

题目链接。

题意

现在有两个长度为 的排列 。

定义一个区间 的权值 。

次询问，每一次给定 ，查询 。

。

题解

首先有一些比较套路的思考虽然我也不会。

就是考虑把每一个询问挂在对应的 上，然后使用线段树维护一些信息。

大概每一个位置 需要维护一个 表示 里 的最大值， 同理。

然后一个 需要回答的大概就是从左到右扫到 的时候， 这段区间内 的历史和。

然后考虑需要维护什么东西呢。

首先肯定需要维护 表示一个区间的历史和以及 。

然后我们中间会有给 区间加的操作，所以还需要维护 tag。

然后区间加操作还会对 以及 产生影响，又需要记 表示区间的 和以及长度。

现在已经知道需要维护的东西是 五个量，考虑 tag 怎么办。

考虑写成矩阵的形式。

操作有三种，区间加 ，区间加 ，以及贡献一次历史和。

那么容易发现，操作一定可以写成这样子： 那么这说明 tag 可以使用 个变量来表示，那直接做就好了。

问题的本质在于构造出两个群 ，并构造出运算 。

本题中需要先观察 的构造，然后矩阵拆拆拆就可以搞出剩下的东西。

时间复杂度 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
using ull=unsigned long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct M
{
    ull Txy,Tx,Ty,T,tx,ty,t;
    M(ull Txy=0,ull Tx=0,ull Ty=0,ull T=0,ull tx=0,ull ty=0,ull t=0):
        Txy(Txy),Tx(Tx),Ty(Ty),T(T),tx(tx),ty(ty),t(t){}
}tag[1000001];
struct D
{
    ull ans,Sxy,Sx,Sy,S;
    D(ull ans=0,ull Sxy=0,ull Sx=0,ull Sy=0,ull S=0):ans(ans),Sxy(Sxy),Sx(Sx),Sy(Sy),S(S){}
    inline void output(char c='\n')
    {
        printf("ans=%llu Sxy=%llu Sx=%llu Sy=%llu S=%llu\n",ans,Sxy,Sx,Sy,S);
    }
}num[1000001];
D operator + (D L,D R)
{
    return D(L.ans+R.ans,L.Sxy+R.Sxy,L.Sx+R.Sx,L.Sy+R.Sy,L.S+R.S);
}
D operator * (D a,M b)
{
    a.ans+=b.Txy*a.Sxy+b.Tx*a.Sx+b.Ty*a.Sy+b.T*a.S;
    a.Sxy+=b.tx*a.Sx+b.ty*a.Sy+b.t*a.S;
    a.Sx+=b.ty*a.S,a.Sy+=b.tx*a.S;
    return a;
}
M operator * (M b,M c)
{
    M d;
    d.Txy=b.Txy+c.Txy;
    d.Tx=b.Tx+b.tx*c.Txy+c.Tx;
    d.Ty=b.Ty+b.ty*c.Txy+c.Ty;
    d.T=b.T+b.t*c.Txy+b.ty*c.Tx+b.tx*c.Ty+c.T;
    d.tx=b.tx+c.tx;
    d.ty=b.ty+c.ty;
    d.t=b.t+b.ty*c.tx+b.tx*c.ty+c.t;
    return d;
}
struct node{ int l,r;}q[250001];
ull qans[250001];
int sta[250001],toa;
int stb[250001],tob;
vc<int>nod[250001];
int a[250001];
int b[250001];
int n,m;
inline void T(int p,M y)
{
    num[p]=num[p]*y;
    tag[p]=tag[p]*y;
}
inline void push_down(int p)
{
    T(p*2,tag[p]),T(p*2|1,tag[p]);
    tag[p]=M();
}
inline void push_up(int p){ num[p]=num[p*2]+num[p*2|1];}
void build(int p,int pl,int pr)
{
    num[p].S=pr-pl+1;
    if(pl==pr) return ;
    int mid=(pl+pr)>>1;
    build(p*2,pl,mid);
    build(p*2|1,mid+1,pr);
}
void add(int p,int pl,int pr,int l,int r,M y)
{
    if(l<=pl&&pr<=r){ T(p,y);return ;}
    int mid=(pl+pr)>>1;push_down(p);
    if(l<=mid) add(p*2,pl,mid,l,r,y);
    if(mid<r) add(p*2|1,mid+1,pr,l,r,y);
    push_up(p);
}
D get(int p,int pl,int pr,int l,int r)
{
    if(l<=pl&&pr<=r) return num[p];
    int mid=(pl+pr)>>1;D ans;push_down(p);
    if(l<=mid) ans=ans+get(p*2,pl,mid,l,r);
    if(mid<r) ans=ans+get(p*2|1,mid+1,pr,l,r);
    return ans;
}
int main()
{
    read();n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    build(1,1,n);
    m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].l=read(),q[i].r=read();
        nod[q[i].r].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        while(toa&&a[i]>a[sta[toa]]) add(1,1,n,sta[toa-1]+1,sta[toa],M(0,0,0,0,0,a[i]-a[sta[toa]],0)),toa--;
        while(tob&&b[i]>b[stb[tob]]) add(1,1,n,stb[tob-1]+1,stb[tob],M(0,0,0,0,b[i]-b[stb[tob]],0,0)),tob--;
        sta[++toa]=stb[++tob]=i;add(1,1,n,i,i,M(0,0,0,0,0,a[i],0)*M(0,0,0,0,b[i],0,0));
        add(1,1,n,1,n,M(1,0,0,0,0,0,0));

        for(int id:nod[i])
        {
            D val=get(1,1,n,q[id].l,q[id].r);
            qans[id]=val.ans;
        }
    }
    for(int i=1;i<=m;i++) printf("%llu\n",qans[i]);
    return 0;
}