HS
AFO
HS的博客
LOJ2736「JOISC 2016 Day 3」回转寿司

题目链接

LOJ

题目描述

给出一个有$N$个点的环,环上各点有一个初始权值$a_i$ 。

给出$Q$个询问,每次询问给出一个区间$[l,r]$和一个值$A$ ,对于$A$的变动定义如下($r$可能会小于$l$因为是环形):

for (int i = l; i <= r; i++) if(a[i] > A) swap(a[i],A);

对于每个询问,回答遍历完区间$[l,r]$后$A$的最终值。

注:我们按逆时针方向在环上编号,并规定$[l,r]$为从位置编号为$l$的点逆时针遍历至位置编号为$r$的点所经过点的集合。

输入格式

第一行包括两个数 $N$ 与 $Q$ 表示环的大小和询问的个数;
之后的 $N$ 行每行为一个整数,第 $i$ 个为 $a_i$;
之后的 $Q$ 行每行有三个整数 $l_i$ 、$r_i$ 、$A_i$,表示如上所示。

输出格式

输出包括$Q$行,每行包括一个数,为变动结束后$A_i$的值。

输入输出样例

输入 #1

6 7
8
6
7
4
5
9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3

输出 #1

7
9
8
7
8
6
5

输入 #2

4 2
5
2
4
7
1 4 3
1 4 1

输出 #2

7
5

输入 #3

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

输出 #3

19
10
14
17
8
10
3
12
7
9

说明/提示

$1 \le N \le 4 \times 10^5 , 1 \le Q \le 25000, 1 \le a_i \le 10^9, 1 \le l,r \le N, 1 \le A \le 10^9$

分析

首先分块。
每次操作之后$A$一定会变成操作区间的最大值,所以直接对每个块维护一个大根堆。
由于涉及到整块修改,所以要打标记。
对于一次修改,相当于将整个操作区间中大于$A$的数全部右移,所以从可以左至右扫一遍,每次更新修改的值(标记)。
发现对于一个位置,如果有多次修改,那它一定会变成这些修改中最小的那一个。
所以释放标记的时候,用小根堆维护标记,每次修改然后更新标记。
整块用维护好的大根堆更新,边角释放标记之后直接暴力。
时间复杂度 $O(n\sqrt nlog sqrt n)$ ,空间复杂度 $O(n\sqrt n)$。

一些对我而言的坑

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define maxn 400010
#define maxb 700
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,m,B,a[maxn],bel[maxn],L[maxb],R[maxb];
priority_queue<int>val[maxb];
priority_queue<int,vector<int>,greater<int>>tag[maxb];
void down(int k)
{
    if(tag[k].empty())
        return ;
    for(int i=L[k];i<=R[k];i++)
    {
        if(a[i]>tag[k].top())
        {
            tag[k].push(a[i]);
            a[i]=tag[k].top();
            tag[k].pop();
        }
    }
    while(!tag[k].empty())
        tag[k].pop();
}
void change(int k,int l,int r,int &A)
{
    down(k);
    for(int i=l;i<=r;i++)
        if(a[i]>A)
            swap(a[i],A);
    while(!val[k].empty())
        val[k].pop();
    for(int i=L[k];i<=R[k];i++)
        val[k].push(a[i]);
}
void change(int l,int r,int &A)
{
    if(bel[l]==bel[r])
    {
        change(bel[l],l,r,A);
        return ;
    }
    change(bel[l],l,R[bel[l]],A);
    for(int i=bel[l]+1;i<bel[r];i++)
        if(val[i].top()>A)
        {
            tag[i].push(A); 
            val[i].push(A);
            A=val[i].top();
            val[i].pop();
        }
    change(bel[r],L[bel[r]],r,A);
}
int main()
{
    read(n,m);
    B=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        bel[i]=(i-1)/B+1;
        val[bel[i]].push(a[i]);
    }
    for(int i=1;i<=bel[n];i++)
    {
        L[i]=(i-1)*B+1;
        R[i]=i*B;
    }
    R[bel[n]]=n;
    for(int i=1;i<=m;i++)
    {
        int l,r,A;
        read(l,r,A);
        if(l<=r)
        {
            change(l,r,A);
        }
        else
        {
            change(l,n,A);
            change(1,r,A);
        }
        printf("%dn",A);
    }
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

LOJ2736「JOISC 2016 Day 3」回转寿司
分块+堆
扫描二维码继续阅读
2020-01-11