题解
修改玫瑰 \(i\) ,对答案的影响是:
减去只有玫瑰 \(i\) 的区间,加上只有玫瑰 \(i\) 和另一个玫瑰的区间,加上 m
因此我们对每个玫瑰 \(i\) ,维护上述两个区间长度
由于每个玫瑰开花时间一样,所以我们可以用扫描线的思想,对所有区间的端点离散化排序,然后升序遍历,由于开花时间一样,所以我们可以用队列维护当前区间(当前端点到下一端点)的玫瑰
只有一朵玫瑰,或者两朵玫瑰时维护上述值
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
#define lb long double
#define lowbit(x) ((x)&(-x))
const ll inf=1e18;
const ll mod=1e9+7;
const ll N=4e5;
ll qpow(ll a,ll n)
{
ll res=1;
while(n)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
ll inv(ll x)
{
return qpow(x,mod-2);
}
ll fa[2000005];
ll finds(ll now){return now==fa[now]?now:finds(fa[now]);}
vector<ll> G[200005];
ll dfn[200005],low[200005];
ll cnt=0,num=0;
ll in_st[200005]={0};
stack<ll> st;
ll belong[200005]={0};
void scc(ll now,ll fa)
{
dfn[now]=++cnt;
low[now]=dfn[now];
in_st[now]=1;
st.push(now);
for(auto next:G[now])
{
if(next==fa) continue;
if(!dfn[next])
{
scc(next,now);
low[now]=min(low[now],low[next]);
}
else if(in_st[next])
{
low[now]=min(low[now],dfn[next]);
}
}
if(low[now]==dfn[now])
{
ll x;
num++;
do
{
x=st.top();
st.pop();
in_st[x]=0;
belong[x]=num;
}while(x!=now);
}
}
*/
int poi[400005];
int sum[200005][3]={0};
int t[200005];
void solve()
{
int n,m;
cin>>n>>m;
int tot=0;
int cnt=0;
for(int i=1;i<=n;i++)
{
cin>>t[i];
poi[++cnt]=t[i];
poi[++cnt]=t[i]+m;
}
sort(t+1,t+1+n);
sort(poi+1,poi+1+cnt);
int len=unique(poi+1,poi+1+cnt)-poi-1;
queue<int> q;
int it=1;
for(int i=1;i<=len;i++)
{
while(q.size()&&t[q.front()]+m<=poi[i]) q.pop();
while(it<=n&&t[it]==poi[i]) q.push(it++);
//printf("i:%d poi:%d it:%d\n",i,poi[i],it);
if(q.size()==1)
{
sum[q.front()][1]+=poi[i+1]-poi[i];
tot+=poi[i+1]-poi[i];
}
if(q.size()==2)
{
sum[q.front()][2]+=poi[i+1]-poi[i];
sum[q.back()][2]+=poi[i+1]-poi[i];
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
//printf("i:%d sum1:%d sum2:%d\n",i,sum[i][1],sum[i][2]);
ans=max(ans,tot-sum[i][1]+sum[i][2]+m);
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TT=1;
//cin>>TT;
while(TT--) solve();
return 0;
}
标签:P10837,int,ll,st,云音泛,low,poi,FLA,now
From: https://www.cnblogs.com/pure4knowledge/p/18342946