风力观测解题报告

发表于 | 分类于 |

写在前面

啊因为这段时间一直很忙，所以好久没有更新博客了。

这次正好在校队训练的时候做掉了这个非常具有启发意义的题目，所以写上来分享一下。

题目

传送门

题目大意：维护一个数列，支持区间加，区间减，查询某个位置的历史绝对值最大值。

做法

历史绝对值最大值，可以通过维护最大值和最小值来解决，下面我们仅考虑最大值，最小值同理。

这是一个很好的扫描线的题目，一般而言，对于区间修改，单点查询的可离线题目，我们可以通过扫描线解决。

先离线所有操作，然后考虑在区间的左端点加入这个操作，右端点删除这个操作。

我们考虑该操作对区间内的贡献，每个操作对应了时间线段树上的一个位置，那么每个时刻该扫描线位置的历史值对应了时间区间上的一个前缀和。

那么我们考虑直接维护这个前缀和，任意时刻加入删除一个数的操作可以看成对时间区间的区间加和区间减，同时我们维护时间区间的每个点的最大值即可。

这样对于每个查询对应的时间，我们查询在这个时间点之前的时间区间内的最大值即可，用支持区间修改的线段树即可维护。

代码

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

/*****************************************
Author: lizi
Email: lzy960601@outlook.com
****************************************/
  
#include<bits/stdc++.h>
  
using namespace std;
  
const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;
  
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define sec second
#define fir first

typedef pair<LL,LL> pll;
typedef pair<int,int> pii;

const int maxn=100005;
int a[maxn],n,q,T;
LL ans[maxn];
vector< pii > g1[maxn],g2[maxn],qu[maxn];

struct segtree
{
    struct node
    {
        int ls,rs,lg,rg,mid;
        LL mi,ma,tag;
        void cle(){ls=rs=lg=rg=mid=mi=ma=tag=0;}
        bool one(){return lg==rg;}
        bool judge(int x,int y){return lg==x && rg==y;}
    }tr[200005];
    int k;

    void pushup(int x)
    {
        int ls=tr[x].ls,rs=tr[x].rs;
        if(ls+rs<=0)return;
        tr[x].mi=min(tr[ls].mi,tr[rs].mi);
        tr[x].ma=max(tr[ls].ma,tr[rs].ma);
    }
    
    void pushdown(int x)
    {
        int ls=tr[x].ls,rs=tr[x].rs;
        if(ls+rs<=0 || tr[x].tag==0)return;
        LL tag=tr[x].tag;
        tr[x].tag=0;
        tr[ls].tag+=tag;tr[rs].tag+=tag;
        tr[ls].mi+=tag;tr[ls].ma+=tag;
        tr[rs].mi+=tag;tr[rs].ma+=tag;
        pushup(x);
    }

    void mt(int x,int y)
    {
        tr[k].cle();
        tr[k].lg=x;tr[k].rg=y;
        if(x==y)return;
        int mid=(x+y)>>1,t=k;
        tr[k].mid=mid;
        k++;tr[t].ls=k;mt(x,mid);
        k++;tr[t].rs=k;mt(mid+1,y);
        pushup(t);
    }
    
    void init(int n){k=1;mt(0,n);}

    void add(int now,int x,int y,LL nu)
    {
        if(tr[now].judge(x,y))
        {
            tr[now].tag+=nu;
            tr[now].ma+=nu;
            tr[now].mi+=nu;
            return;
        }
        pushdown(now);
        int mid=tr[now].mid;
        if(x<=mid)add(tr[now].ls,x,min(mid,y),nu);
        if(y>mid)add(tr[now].rs,max(x,mid+1),y,nu);
        pushup(now);
    }

    pll query(int now,int x,int y)
    {
        if(tr[now].judge(x,y))return mp(tr[now].mi,tr[now].ma);
        int mid=tr[now].mid;
        pushdown(now);
        if(y<=mid)return query(tr[now].ls,x,y);
        if(x>mid)return query(tr[now].rs,x,y);
        pll u=query(tr[now].ls,x,mid);
        pll v=query(tr[now].rs,mid+1,y);
        return mp(min(u.fir,v.fir),max(u.sec,v.sec));
    }
}segt;

int main()
{
    IN;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&q);
        int cnt=0;
        for(int i=1;i<=n;i++)g1[i].clear(),g2[i].clear(),qu[i].clear();
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            g1[i].pb(mp(a[i],0));
            g2[i].pb(mp(a[i],0));
        }
        for(int i=1;i<=q;i++)
        {
            int opt,nu;
            scanf("%d",&opt);
            if(opt==1)
            {
                int l,r;
                scanf("%d%d%d",&l,&r,&nu);
                g1[l].pb(mp(nu,i));
                g2[r].pb(mp(nu,i));
            }else
            {
                scanf("%d",&nu);
                qu[nu].pb(mp(i,++cnt));
            }
        }
        segt.init(q);
        for(int mask=1;mask<=n;mask++)
        {
            for(pii p : g1[mask])
            {segt.add(1,p.sec,q,p.fir);}
            for(pii p : qu[mask])
            {
                pll temp=segt.query(1,0,p.fir);
                //printf("%d %d %d\n",mask,p.fir,p.sec);
                ans[p.sec]=max(abs(temp.fir),abs(temp.sec));
            }
            for(pii p : g2[mask])
            {segt.add(1,p.sec,q,-p.fir);}
        }
        for(int i=1;i<=cnt;i++)printf("%lld\n",ans[i]);
    }
    return 0;
}
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多