Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

https://codeforces.com/contest/1864

F. Exotic Queries

题意

给定一个长度为 $n$ 的数组 $a$，共有 $q$ 次询问，每次询问一个区间 $[l,r]$：每次操作可以选定一个区间，将区间内所有数减去任意一个数。要求最终所有的数组中大小在 $[l,r]$ 内的数都恰好变为 $0$，且所有选择的区间要么不交，要么包含，求最小操作次数。

数据范围：$1\leq n,q\leq 10^6$。

题解

感觉是一道很好的数据结构！

首先考虑 $a_x=a_y(x<y)$，当它们中间没有比它们小的数时，可以将它们一起变为 $0$，否则就要多一次操作。当加上区间 $[l,r]$ 的限制后，记 $t$ 为 $(x,y)$ 内的最大数，当且仅当 $l\leq t$ 时会增加一次操作。所以可以考虑将所有询问离线下来，从小到大一次将 $a$ 插入进去。利用线段树维护区间最值，树状数组维护左端点对应的答案。考虑插入的值为 $i,a_x=a_y=i$，记 $t=\max(a_{x+1},\cdots,a_{y-1})$，那么对于所有的 $l\in[1,t]$ 都会增加一次操作。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+5;
int n,q,a[N],cnt[N];
ll ans[N];
vector<int> pos[N];
vector<pii> qry[N];
int c[N];
int lowbit(int x) {return x&-x;}
void add(int x,int k)
{
    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
void add(int l,int r,int k) {add(l,k),add(r+1,-k);}
ll query(int x)
{
    ll ans=0;
    while(x)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int tr[4*N];
void update(int x,int k,int l,int r,int p)
{
	if(l==x&&r==x)
    {
        tr[p]=k;
        return ;
    }
    int m=l+((r-l)>>1);
    if(x<=m) update(x,k,l,m,p*2);
    if(x>m) update(x,k,m+1,r,p*2+1);
    tr[p]=max(tr[p*2],tr[p*2+1]);
}
int query(int ql,int qr,int l,int r,int p)
{
    if(ql<=l&&qr>=r) return tr[p];
    int m=l+((r-l)>>1);
    int mx=0;
	if(ql<=m) mx=max(mx,query(ql,qr,l,m,p*2));
	if(qr>m) mx=max(mx,query(ql,qr,m+1,r,p*2+1));
	return mx;    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        pos[a[i]].push_back(i);
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;cin>>l>>r;
        qry[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++)
    {
        cnt[i]=cnt[i-1];
        if(!pos[i].empty())
        {
            cnt[i]++;
            update(pos[i][0],i,1,n,1);
            for(int j=1;j<(int)pos[i].size();j++)
            {
                int x=pos[i][j-1]+1,y=pos[i][j]-1;
                if(x<=y) add(1,query(x,y,1,n,1),1);
                update(pos[i][j],i,1,n,1);
            }   
        }
        for(auto p:qry[i]) 
        {
            int l=p.first;
            ans[p.second]=cnt[i]-cnt[l-1]+query(l);
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}