题目链接
解题思路
发现向前移的部分普通维护比较困难,因此我们考虑通过某种方式来维护这个东西。
考虑建立 \(m\) 个虚点来维护,每次询问都将实点移至虚点去。这里求答案我们需要支持单点加,区间求和,可以用树状数组轻松维护。
参考代码
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}
template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}
ll _t_;
void _clear(){}
ll n,m;
ll pos[1000010];
ll q[1000010];
ll tree[1000010];
ll last;
ll ans1[1000010],ans2[1000010];
void add(ll x,ll y)
{
if(x==0)
return ;
for(;x<=1e6+5;x+=lowbit(x))
tree[x]+=y;
}
ll query(ll x)
{
ll sum=0;
for(;x;x-=lowbit(x))
sum+=tree[x];
return sum;
}
void solve()
{
_clear();
cin>>n>>m;
last=m;
forl(i,1,m)
cin>>q[i];
forl(i,1,n)
pos[i]=m+i;
forl(i,1,n)
ans1[i]=ans2[i]=i;
forl(i,1,n)
add(pos[i],1);
forl(i,1,m)
{
Max(ans2[q[i]],query(pos[q[i]]));
add(pos[q[i]],-1);
pos[q[i]]=last--;
ans1[q[i]]=1;
add(pos[q[i]],1);
}
forl(i,1,n)
Min(ans1[i],query(pos[i])),
Max(ans2[i],query(pos[i]));
forl(i,1,n)
cout<<ans1[i]<<' '<<ans2[i]<<endl;
}
int main()
{
// freopen("tst.txt","r",stdin);
// freopen("sans.txt","w",stdout);
IOS;
_t_=1;
// cin>>_t_;
while(_t_--)
solve();
QwQ;
}
标签:forl,pos,CF1288E,add,query,杂题,define
From: https://www.cnblogs.com/wangmarui/p/18540501