专栏文章

题解：P11286 [COTS 2017] 盗道 Krimošten

EEityDawn
P11286题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir3t2pb
此快照首次捕获于
2025/12/04 15:17
3 个月前
此快照最后确认于
2025/12/04 15:17
3 个月前
查看原文

思路

对于全局来讲，我们维护一个 bib_i 序列，其中初始时 bi=ib_i=i，表示盗贼初始有 ii 块钱经过操作后所拥有的钱数。
而每一个位置上的数 aia_i，对应操作为将 bb 中 bj<aib_j < a_i 的变成 bj+1b_j+1，bj>aib_j>a_i 的变成 bj−1b_j-1，可以打表发现 bib_i 是单调不降的，这是一个很重要的性质。
再看区间怎么做。考虑扫描线，还是维护 bib_i。
对于修改操作，bib_i 是单调不降的，可以拿线段树维护 bib_i，转化为线段树上二分，区间加。
对于询问 (l,r,k)(l,r,k)，现在假设我们已经扫完了 [1,l−1][1,l-1] 的所有 aia_i 并进行了操作，那么在 bb 中找一个位置满足 bi=kb_i=k，可以线段树二分。这里可以看成是找一个初始钱数为 kk 的位置。再扫描到 rr 时，直接询问记录位置的值即可，等价于初始钱数为 kk，操作完 [l,r][l,r] 后的值。而为了让 bib_i 中 [0,106][0,10^6] 的值都存在，可以让 bi=i,i∈[−106,2×106]b_i=i,i\in[-10^6,2\times10^6]。
时间复杂度是 O(nlog⁡V)O(n\log V) 的。

code

CPP
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define mset(x,y) memset((x),(y),sizeof((x)))
#define mcpy(x,y) memcpy((x),(y),sizeof((y)))
#define FileIn(x) freopen(""#x".in","r",stdin)
#define FileOut(x) freopen(""#x".out","w",stdout)
#define debug(x) cerr<<""#x" = "<<(x)<<'\n'
#define Assert(x) if(!(x)) cerr<<"Failed: "#x" at line "<<__LINE__,exit(1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Int;
const int N=5e5+10;
const int V=1e6,M=3e6+10;
bool StM;
int n,m,c[N],pos[N];
vector<int>qr[N];
vector<pair<int,int>>ql[N];
int ma[M<<2],tag[M<<2],Ans[N];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
void push_up(int x){ma[x]=max(ma[lc(x)],ma[rc(x)]);}
void addtag(int val,int x){ma[x]+=val,tag[x]+=val;}
void push_down(int x)
{
    if(!tag[x]) return;
    addtag(tag[x],lc(x)),addtag(tag[x],rc(x)),tag[x]=0;
}
void build(int l,int r,int x)
{
    if(l==r)
        return void(ma[x]=l);
    int mid=(l+r)>>1;
    build(l,mid,lc(x)),build(mid+1,r,rc(x));
    return push_up(x);
}
int query(int val,int l=-V,int r=2*V,int x=1)
{
    if(l==r) return l;
    push_down(x);
    int mid=(l+r)>>1;
    if(ma[lc(x)]>=val) return query(val,l,mid,lc(x));
    else return query(val,mid+1,r,rc(x));
}
int Query(int y,int l=-V,int r=2*V,int x=1)
{
    if(l==r)
        return ma[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(y<=mid) return Query(y,l,mid,lc(x));
    else return Query(y,mid+1,r,rc(x));
}
void modify(int p,int q,int val,int l=-V,int r=2*V,int x=1)
{
    Assert(p<=q);
    if(p<=l&&q>=r)
        return addtag(val,x);
    push_down(x);
    int mid=(l+r)>>1;
    if(p<=mid) modify(p,q,val,l,mid,lc(x));
    if(q>mid) modify(p,q,val,mid+1,r,rc(x));
    return push_up(x);
}
void Main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    build(-V,2*V,1);
    for(int id=1,l,r,k;id<=m;id++)
    {
        cin>>l>>r>>k;
        ql[l].push_back({k,id});
        qr[r].push_back(id);
    }
    for(int i=1,x,y;i<=n;i++)
    {
        for(auto [val,id]:ql[i]) pos[id]=query(val);
        x=query(c[i]),y=query(c[i]+1);modify(-V,x-1,1),modify(y,2*V,-1);
        for(auto id:qr[i]) Ans[id]=Query(pos[id]);
    }
    for(int i=1;i<=m;i++) cout<<Ans[i]<<'\n';
}
bool EdM;
int main()
{
    cerr<<fabs(&StM-&EdM)/1024.0/1024.0<<" MB\n";
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int StT=clock();
    int T=1;
    while(T--) Main();
    int EdT=clock();
    cerr<<1e3*(EdT-StT)/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...