C. Klee in Solitary Confinement（2021 南京 ICPC）
C. Klee in Solitary Confinement
观察题目，发现暴力枚举区间不可行。
考虑一个经典套路：独立处理每个数字（考虑一个数字作为众数的时候，只有x和x-k会对答案造成影响，其他是不用考虑的）
于是，考虑把每个数字作为众数
下面是一个样例
1 2 2 3 5 k=2
枚举：
当3作为众数的时候，只有1（3-k）和3本身会对答案造成影响
然后还有一个经典的套路是贡献法
原数列其实就可以堪称
1 0 0 -1 0 （b序列）
意思就是说，如果选了1，等于贡献加一（多了一个三）
如果选了3，贡献就减一（少了一个3----3变成5了）
所以说，实质上，我们就是在求b序列的最大连续区间和
另外对于复杂度来说，我们是对每个数字分别处理，
比如说众数为2的时候，就只考虑2和0的位置有哪些，其他位置是不会对这个造成影响的
然后再考虑一下，每个数字实质上跑了两次（删除一次，增加一次）
所以实质上的复杂度就是（2*P），或者说（3*P-4*P）---（这个要看具体写法了，因为有的时候可能会出现重复的情况）
接下来就到了分岔口了
P的具体时间复杂度是多少呢
1.我的方法是使用一个线段树
该种方法P=nlogn
我当时没想到2那种O（n）的方法，套了一个可以对任意区间求最大连续字段和并可以修改数值的板子，大概是GSS3
当时忘记了这道题的区间是1-n随便取了
2.我昨晚还想到一种方法是类似跑一个长度无限大的滑动窗口，或者说小dp，查询一下最大连续字段和即可（就是dp）
注意:需要注意操作方式
比如说对3为众数，那得到遍历的数组实质是是一个
1 -1 （实质数组），这样才能保证复杂度是O（n）
该种方法P=n
3.方法其实很多，官方题解我还没看，但空气力学是用的归并来维护的这个最大连续子段和的，只要会归并就容易看懂，且前置思路就是我上面的说法
4.还有一种前缀和的方法，感觉挺牛的，推式子推出来的，建议看看
https://blog.csdn.net/weixin_51934288/article/details/127087648
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'
const int N=2e6+10;
int a[N];
#define lc (u<<1)
#define rc ((u<<1)|1)
struct Tree{
int lans,rans,sum,ans;
}tr[N*4];
int n,k;
#define mid ((l+r)>>1)
vector<int> cnt[2000000+10];
void pushup(int x){
tr[x].sum = tr[x << 1].sum + tr[(x << 1) | 1].sum;
tr[x].lans = max(tr[x << 1].lans, tr[x << 1].sum + tr[(x << 1) | 1].lans);
tr[x].rans = max(tr[(x << 1) | 1].rans, tr[(x << 1) | 1].sum + tr[x << 1].rans);
tr[x].ans = max(max(tr[x << 1].ans, tr[(x << 1) | 1].ans), tr[x << 1].rans + tr[(x << 1) | 1].lans);
}
void update(int u,int l,int r,int x,int k){
if(l==r){
tr[u].sum=tr[u].lans=tr[u].rans=tr[u].ans=k;return;
}
if(x<=mid) update(lc,l,mid,x,k);
else update(rc,mid+1,r,x,k);
pushup(u);
}
void build(int u,int l,int r){
if(l==r){
tr[u].rans=tr[u].sum=tr[u].ans=tr[u].lans=0;
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
pushup(u);
}
Tree query(int u,int l,int r,int x,int y){
if(x<=l&&r<=y){
return tr[u];
}
if(y<=mid) return query(lc,l,mid,x,y);
if(x>mid) return query(rc,mid+1,r,x,y);
else{
Tree ans,a,b;
a=query(lc,l,mid,x,y),b=query(rc,mid+1,r,x,y);
ans.sum = a.sum + b.sum;
ans.ans = max(max(a.ans, a.rans + b.lans), b.ans);
ans.lans = max(a.lans, a.sum + b.lans);
ans.rans = max(b.rans, b.sum + a.rans);//合并答案
return ans;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
//for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i){
int x;cin>>x;
cnt[x+1000000].push_back(i);
a[x+1000000]++;
}
build(1,0,2e6);
int ans=0;
for(int i=-1e6;i<=1e6;++i){
int now=i+1e6;
ans=max(ans,a[now]);
//int w=cnt[now].size();
//int ww=cnt[now-k].size();
if(!a[now]||!((now-k>=0)&&(now-k<=2e6)&&a[now-k])||k==0) continue;
if(a[now]||((now-k>=0)&&(now-k<=2e6)&&a[now-k])){//来自与now和now-k
if(now-k>=0&&(now-k<=2e6)){
//cout<<now-k<<endl;
for(auto t:cnt[now-k]){
update(1,0,2e6,t,1);
}
}
for(auto t:cnt[now]){
update(1,0,2e6,t,-1);
}
int q=query(1,0,2e6,0,2e6).ans;
ans=max(q+a[now],ans);
if(now-k>=0&&(now-k<=2e6)){
for(auto t:cnt[now-k]){
update(1,0,2e6,t,0);
}
}
for(auto t:cnt[now]){
update(1,0,2e6,t,0);
}
}
}
cout<<ans<<endl;
return 0;
}原文地址：https://blog.csdn.net/why_not_fly/article/details/143021808
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！