P6602 「EZEC-2」数轴
扶苏大神推荐
简要题意
给定一个长度为 的序列，有 次操作，对序列单点加 。每次操作后都要求出序列中最长的区间，满足区间和不大于
From 一扶苏一 /se/se/se
需要注意的是，但是k<=100
首先，我们会发现在直接数轴上DP是不行的，因为，直接去考虑是的？
而数轴上坐标点如此离散的情况下，我们如果想要直接知道一个点之前那个点是什么,可以使用离散化或者链表的方法
而离散化显得很不能扩展，因为只是变成了差不多的做法
而链表可以再有动态变化的情况下维护
所以我们只需要去考虑删除一个数之后用O(k)维护新答案
但是要把整个过程反过来，这样答案单调上升，ans可以直接取max
写的时候注意我们答案是要pre和nxt之间找的,而且设置的头尾还不能减去.....毒毒毒
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using std::lower_bound;
using std::max;
using std::sort;
const int MAXN = 1e6 + 7;
const int inf = 1e9 + 7;
int n, m, k, tot, ans = -1;
int x[MAXN], a[MAXN], A[MAXN];
struct rec {
int x, a;
bool operator<(const rec &l)const {
return x < l.x;
}
bool operator<(const int &l)const {
return x < l;
}
} pt[MAXN], rt[MAXN];
int pre[MAXN], nxt[MAXN];
inline void solve(int x) {
// printf("%d %d\n",x,nxt[x]);
int nw = x;
int y = nw;
int S = rt[x].a;
if(S > k) {
if(pre[x] != 0)
ans = max(rt[x].x - rt[pre[x]].x - 2, ans);
else ans = max(ans, rt[x].x - 1);
if(nxt[x] != tot + 1)
ans = max(rt[nxt[x]].x - rt[x].x - 2, ans);
else ans = max(ans, m - rt[x].x - 1);
// printf("%d %d\n",x,nxt[x]);
// if(x==0 && nxt[x]==tot+1) ans=max(ans,m);
return ;
}
while(S <= k) {
x = pre[x];
if(S + rt[x].a > k) {
// printf("%d %d %d %d %d %d %d\n", nw, x, nxt[nw], tot, rt[nxt[nw]].x, rt[nw].x, rt[x].x);
if(nxt[nw] != tot + 1)
ans = max(rt[nxt[nw]].x - rt[x].x - 2, ans);
else ans = max(rt[nxt[nw]].x - rt[x].x - 1, ans);
// printf("%d\n", ans);
x = nxt[x];
break;
}
S += rt[x].a;
}
while(S <= k) {
y = nxt[y];
if(S + rt[y].a > k ) {
if(pre[x] != 0)
ans = max(rt[y].x - 2 - rt[pre[x]].x, ans);
else ans = max(rt[y].x - 1 - rt[pre[x]].x, ans);
y = pre[y];
break;
}
S += rt[y].a;
}
// printf("%d %d %d\n", nw, x, y);
if(nxt[y]==tot+1 && pre[x]==0)
ans=max(rt[nxt[y]].x-rt[pre[x]].x,ans);
else if(nxt[y]==tot+1||pre[x]==0)
ans=max(rt[nxt[y]].x-rt[pre[x]].x-1,ans);
else {
ans=max(ans,rt[nxt[y]].x-rt[pre[x]].x-2);
}
// puts("qwq");
// assert(x<=nw);
while(x != nw) {
// printf("%d %d!!\n",x,nw);
S -= rt[x].a;
x = nxt[x];
while(S <= k) {
y = nxt[y];
if(S + rt[y].a > k) {
if(y==tot+1 && pre[x]==0)
ans=max(rt[y].x-rt[pre[x]].x,ans);
else if(y==tot+1||pre[x]==0)
ans=max(rt[y].x-rt[pre[x]].x-1,ans);
else {
ans=max(ans,rt[y].x-rt[pre[x]].x-2);
}
y = pre[y];
break;
}
S += rt[y].a;
}
if(nxt[y]==tot+1 && pre[x]==0)
ans=max(rt[nxt[y]].x-rt[pre[x]].x,ans);
else if(nxt[y]==tot+1||pre[x]==0)
ans=max(rt[nxt[y]].x-rt[pre[x]].x-1,ans);
else {
ans=max(ans,rt[nxt[y]].x-rt[pre[x]].x-2);
}
}
return ;
}
inline void init() {
rt[0].a = inf;
rt[0].x = 0;
nxt[0] = 1;
pre[0]=0;
rt[tot + 1].a = inf;
rt[tot + 1].x = m;
pre[tot + 1] = tot;
nxt[tot + 1]=tot + 1;
// printf("!!%d\n",tot);
for(int i = 1; i <= tot; ++i) {
pre[i] = i - 1;
nxt[i] = i + 1;
}
for(int i = 1; i <= tot; ++i) {
solve(i);
}
return;
}
inline void del(int x) {
nxt[pre[x]] = nxt[x];
pre[nxt[x]] = pre[x];
}
int main() {
// freopen("test.in","r",stdin);
// freopen("test1.out","w",stdout);
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &pt[i].x, &pt[i].a);
x[i] = pt[i].x;
a[i] = pt[i].a;
}
// puts("qwq");
sort(pt + 1, pt + n + 1);
for(int i = 1; i <= n; ++i) {
// printf("%d %d\n",pt[i].x,pt[i-1].x);
if(pt[i].x == pt[i + 1].x && i != n + 1) {
pt[i + 1].a += pt[i].a;
} else {
// printf("%d %d\n",pt[i].x,pt[i].)
rt[++tot] = pt[i];
}
}
// puts("!!!");
init();
// puts("QWQ");
// for(int i = 1; i <= tot; ++i) {
// printf("%d %d\n", rt[i].x, rt[i].a);
// }
// printf("%d %d\n", lower_bound(rt + 1, rt + tot + 1, 1) - rt, lower_bound(rt + 1, rt + tot + 1, 0) - rt);
for(int i = n; i >= 1; --i) {
A[i] = ans;
int id = lower_bound(rt + 1, rt + tot + 1, x[i]) - rt;
// printf("%d %d %d??\n", i, id, ans);
// for(int i=0; i!=tot+1; i=nxt[i]) {
// printf("%d! ",i);
// }
// puts("");
rt[id].a -= a[i];
// printf("%d\n",id);
if(rt[id].a == 0) {
del(id);
// printf("%d %dqwq\n",pre[id],nxt[id]);
solve(pre[id]);
solve(nxt[id]);
} else {
solve(id);
}
}
for(int i = 1; i <= n; ++i)
printf("%d\n", A[i]);
return 0;
}