QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425370 | #964. Excluded Min | ZepX_D | RE | 0ms | 0kb | C++14 | 3.7kb | 2024-05-30 09:48:47 | 2024-05-30 09:48:51 |
answer
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e5+5;
int a[N];
struct que{int l,r,id;}q[N];
vector < int > ve[N];
bool cmp(que a,que b)
{return a.l == b.l ? a.r > b.r : a.l < b.l;}
struct tree{int l,r,mx,laz;}tr[N<<2],t1[N<<2];
void build(int l,int r,int i)
{
tr[i].l = l,tr[i].r = r;
if(l == r) return (void)(tr[i].mx = q[l].r);
int mid = (l+r)>>1;
build(l,mid,i<<1),build(mid+1,r,i<<1|1);
tr[i].mx = max(tr[i<<1].mx,tr[i<<1|1].mx);
}
void M(int p,int i)
{
if(tr[i].l == tr[i].r) return (void)(tr[i].mx = -1e9);
if(p <= tr[i<<1].r) M(p,i<<1);
else M(p,i<<1|1);
tr[i].mx = max(tr[i<<1].mx,tr[i<<1|1].mx);
}
int Q(int l,int r,int k,int i)
{
if(tr[i].l > r || tr[i].r < l) return 0;
if(tr[i].l == tr[i].r) return tr[i].l;
if(tr[i<<1].mx > k) return Q(l,r,k,i<<1);
if(tr[i<<1|1].mx > k) return Q(l,r,k,i<<1|1);
return 0;
}
void B(int l,int r,int i)
{
t1[i].l = l,t1[i].r = r;
if(l == r) return ;
int mid = (l+r)>>1;
B(l,mid,i<<1),B(mid+1,r,i<<1|1);
}
void down(int i)
{
t1[i<<1].mx += t1[i].laz,t1[i<<1|1].mx += t1[i].laz;
t1[i<<1].laz += t1[i].laz,t1[i<<1|1].laz += t1[i].laz;
t1[i].laz = 0;
}
void M1(int l,int r,int i)
{
if(t1[i].l >= l && t1[i].r <= r)
return (void)(t1[i].mx--,t1[i].laz--);
if(t1[i].laz) down(i);
if(t1[i<<1].r >= l) M1(l,r,i<<1);
if(t1[i<<1|1].l <= r) M1(l,r,i<<1|1);
t1[i].mx = max(t1[i<<1].mx,t1[i<<1|1].mx);
}
void M2(int p,int k,int i)
{
if(t1[i].l == t1[i].r)
return (void)(t1[i].mx = k);
if(t1[i].laz) down(i);
if(p <= tr[i<<1].r) M2(p,k,i<<1);
else M2(p,k,i<<1|1);
t1[i].mx = max(t1[i<<1].mx,t1[i<<1|1].mx);
}
vector < int > v,tmp;
int c[N],ans[N],n,t;
void A(int i,int k)
{while(i <= n) c[i] += k,i += i&-i;}
int Q1(int i)
{
int res = 0;
while(i) res += c[i],i -= i&-i;
return res;
}
int getl(int k)
{
int l = 0,r = v.size();
while(l < r)
{
int mid = (l+r)>>1;
if(q[v[mid]].r < k) l = mid+1;
else r = mid;
}
return l;
}
int getr(int k)
{
int l = -1,r = v.size()-1;
while(l < r)
{
int mid = (l+r+1)>>1;
if(q[v[mid]].l > k) r = mid-1;
else l = mid;
}
return l;
}
void D(int k,int i)
{
if(t1[i].l == t1[i].r)
{
t1[i].mx = -1e9;ans[q[t1[i].l].id] = k;
int r = upper_bound(begin(v),end(v),t1[i].l)-begin(v),l = lower_bound(begin(v),end(v),t1[i].l)-begin(v)-1;
l = l < 0 ? 0 : v[l];r = (r == v.size()) ? t : v[r];
int las = q[l].r;
while(1)
{
int id = Q(l+1,r,las,1);
if(!id) break;
M(id,1);
int s = Q1(q[id].r)-Q1(q[id].l-1);
if(s >= k) {ans[q[id].id] = k;continue;}
M2(id,s,1);l = id,las = q[id].r;tmp.pb(id);
}
v.erase(lower_bound(begin(v),end(v),t1[i].l));
for (int j : tmp) v.insert(lower_bound(begin(v),end(v),j),j);
tmp.clear();
return ;
}
if(t1[i].laz) down(i);
if(t1[i<<1].mx >= k) D(k,i<<1);
if(t1[i<<1|1].mx >= k) D(k,i<<1|1);
t1[i].mx = max(t1[i<<1].mx,t1[i<<1|1].mx);
}
int main()
{
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
// ios::sync_with_stdio(0);
cin >> n >> t;
for (int i = 1;i <= n;i++)
{
cin >> a[i],ve[a[i]+1].pb(i);
if(a[i]+1 <= n) A(i,1);
}
for (int i = 1;i <= t;i++)
cin >> q[i].l >> q[i].r,q[i].id = i;
sort(q+1,q+t+1,cmp);
build(1,t,1);B(1,t,1);
int k = n,las = 0,l = 0;
while(1)
{
int id = Q(l+1,t,las,1);
if(!id) break;
M(id,1);
int s = Q1(q[id].r)-Q1(q[id].l-1);
if(s >= k){ans[q[id].id] = k;continue;}
M2(id,s,1);l = id,las = q[id].r;v.pb(id);
}
while(k)
{
for (auto i : ve[k])
{
int L = getl(i),R = getr(i);
if(L <= R) M1(v[L],v[R],1);
A(i,-1);
}
k--;
if(!k) break;
D(k,1);
}
for (int i = 1;i <= t;i++) cout << ans[i] << '\n';
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
3 3 0 0 2 1 3 2 3 3 3