5_Lei @ 2022-09-23 07:41:06
数组版:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4+5;
typedef long long ll;
#define ls(rt) son[rt][0]
#define rs(rt) son[rt][1]
ll R()
{
ll x = 0,f = 1;
char c = getchar();
while(c>'9' || c<'0')
{
if(c=='-')f=-1;
c = getchar();
}
while(c>='0' && c<='9')
{
x = (x<<1)+(x<<3)+(c^48);
c = getchar();
}
return x*f;
}
struct Tree
{
ll sum,lmx,rmx;
Tree(){sum = lmx = rmx = 0;}
}t[maxn<<5];
ll n,cnt,tot,a[maxn],b[maxn],c[10],rt[maxn],son[maxn<<5][2];
vector<ll>pos[maxn];
Tree operator + (const Tree &a,const Tree &b)
{
Tree c;
c.sum = a.sum + b.sum;
c.lmx = max(a.lmx,a.sum + b.lmx);
c.rmx = max(b.rmx,b.sum + a.rmx);
return c;
}
void pushup(ll rt){t[rt] = t[ls(rt)] + t[rs(rt)];}
void build(ll &rt,ll l,ll r)
{
int lst = rt;rt = ++tot;
t[rt] = t[lst];
if(l==r)
{
t[rt].sum = 1,t[rt].lmx = 1,t[rt].rmx = 1;
return;
}
ll mid = (l+r)>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
pushup(rt);
}
void update(ll &rt,ll l,ll r,ll x,ll d)
{
int lst = rt;rt = ++tot;
t[rt] = t[lst];
ls(rt) = ls(lst),rs(rt) = rs(lst);
if(l == r)
{
t[rt].sum = t[rt].lmx = t[rt].rmx = d;
return;
}
ll mid = (l+r)>>1;
if(x <= mid)update(ls(rt),l,mid,x,d);
else update(rs(rt),mid+1,r,x,d);
pushup(rt);
}
Tree query(ll rt,ll l,ll r,ll L,ll R)
{
if(L <= l && r <= R)return t[rt];
ll mid = (l+r)>>1;
if(R <= mid)return query(ls(rt),l,mid,L,R);
else if(mid < L)return query(rs(rt),mid+1,r,L,R);
else return query(ls(rt),l,mid,L,R) + query(rs(rt),mid+1,r,L,R);
}
bool Query(ll rt,ll a,ll b,ll c,ll d)
{
ll sum = 0;
if(b+1 <= c-1)sum += query(rt,1,n,b+1,c-1).sum;
sum += query(rt,1,n,a,b).rmx;
sum += query(rt,1,n,c,d).lmx;
return sum >= 0;
}
void Lei()
{
n = R();
for(int i = 1 ; i <= n ; i++)a[i] = R(),b[i] = a[i];
sort(b+1,b+n+1);
cnt = unique(b+1,b+n+1)-b-1;
for(int i = 1 ; i <= n ; i++)
{
a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
pos[a[i]].push_back(i);
}
build(rt[1],1,n);
for(int i = 2 ; i <= cnt ; i++)
{
rt[i] = rt[i-1];
for(int j = 0 ; j < pos[i-1].size() ; j++)
update(rt[i],1,n,pos[i-1][j],-1);
}
ll Q = R(),last = 0;
for(int i = 1 ; i <= Q ; i++)
{
c[1] = (R()+last)%n;
c[2] = (R()+last)%n;
c[3] = (R()+last)%n;
c[4] = (R()+last)%n;
sort(c+1,c+5);
c[1] += 1,c[2] += 1,c[3] += 1,c[4] += 1;
ll l = 1,r = n,ans = 1;
while(l <= r)
{
ll mid = (l+r)>>1;
if(Query(rt[mid],c[1],c[2],c[3],c[4]))l = mid+1,ans = mid;
else r = mid-1;
}
printf("%lld\n",last = b[ans]);
}
}
int main()
{
Lei();
return 0;
}
结构体版:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4+5;
typedef long long ll;
#define ls(rt) t[rt].lson
#define rs(rt) t[rt].rson
ll R()
{
ll x = 0,f = 1;
char c = getchar();
while(c>'9' || c<'0')
{
if(c=='-')f=-1;
c = getchar();
}
while(c>='0' && c<='9')
{
x = (x<<1)+(x<<3)+(c^48);
c = getchar();
}
return x*f;
}
struct Tree
{
ll lson,rson,sum,lmx,rmx;
Tree(){lson = rson = sum = lmx = rmx = 0;}
}t[maxn<<8];
ll n,cnt,tot,a[maxn],b[maxn],c[10],rt[maxn];
vector<ll>pos[maxn];
Tree operator + (const Tree &a,const Tree &b)
{
Tree c;
c.sum = a.sum + b.sum;
c.lmx = max(a.lmx,a.sum + b.lmx);
c.rmx = max(b.rmx,b.sum + a.rmx);
return c;
}
void pushup(ll rt){t[rt] = t[ls(rt)] + t[rs(rt)];}
void build(ll &rt,ll l,ll r)
{
int lst = rt;rt = ++tot;
t[rt] = t[lst];
if(l==r)
{
t[rt].sum = 1,t[rt].lmx = 1,t[rt].rmx = 1;
return;
}
ll mid = (l+r)>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
pushup(rt);
}
void update(ll &rt,ll l,ll r,ll x,ll d)
{
int lst = rt;rt = ++tot;
t[rt] = t[lst];
if(l == r)
{
t[rt].sum = t[rt].lmx = t[rt].rmx = d;
return;
}
ll mid = (l+r)>>1;
if(x <= mid)update(ls(rt),l,mid,x,d);
else update(rs(rt),mid+1,r,x,d);
pushup(rt);
}
Tree query(ll rt,ll l,ll r,ll L,ll R)
{
if(L <= l && r <= R)return t[rt];
ll mid = (l+r)>>1;
if(R <= mid)return query(ls(rt),l,mid,L,R);
else if(mid < L)return query(rs(rt),mid+1,r,L,R);
else return query(ls(rt),l,mid,L,R) + query(rs(rt),mid+1,r,L,R);
}
bool Query(ll rt,ll a,ll b,ll c,ll d)
{
ll sum = 0;
if(b+1 <= c-1)sum += query(rt,1,n,b+1,c-1).sum;
sum += query(rt,1,n,a,b).rmx;
sum += query(rt,1,n,c,d).lmx;
return sum >= 0;
}
void Lei()
{
n = R();
for(int i = 1 ; i <= n ; i++)a[i] = R(),b[i] = a[i];
sort(b+1,b+n+1);
cnt = unique(b+1,b+n+1)-b-1;
for(int i = 1 ; i <= n ; i++)
{
a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
pos[a[i]].push_back(i);
}
build(rt[1],1,n);
for(int i = 2 ; i <= cnt ; i++)
{
rt[i] = rt[i-1];
for(int j = 0 ; j < pos[i-1].size() ; j++)
update(rt[i],1,n,pos[i-1][j],-1);
}
ll Q = R(),last = 0;
for(int i = 1 ; i <= Q ; i++)
{
c[1] = (R()+last)%n;
c[2] = (R()+last)%n;
c[3] = (R()+last)%n;
c[4] = (R()+last)%n;
sort(c+1,c+5);
c[1] += 1,c[2] += 1,c[3] += 1,c[4] += 1;
ll l = 1,r = n,ans = 1;
while(l <= r)
{
ll mid = (l+r)>>1;
if(Query(rt[mid],c[1],c[2],c[3],c[4]))l = mid+1,ans = mid;
else r = mid-1;
}
printf("%lld\n",last = b[ans]);
}
}
int main()
{
Lei();
return 0;
}
by Error_Eric @ 2022-09-23 08:40:33
@5_Lei 你 lson 在哪里赋值过了.jpg
by Error_Eric @ 2022-09-23 08:43:53
@5_Lei 你要么左节点 (rt>>1)
,右节点 (rt>>1|1)
,要么维护一个 cnt
,build()
往下递归之前先 t[rt].lson=++cnt,t[rt].rson=++cnt
。
by 5_Lei @ 2022-09-23 09:15:52
@Error_Eric 蒟蒻写的动态开点,问题已经解决了,是pushup写挂了,结构体没pushup左右儿子,但还是感谢大佬%%%
by Error_Eric @ 2022-09-23 10:54:28
@5_Lei 现在是我不会了/kk,动态开点不是要开点的时候手动维护左右儿子吗,为什么没见到你维护左右儿子呢/kk?
by Error_Eric @ 2022-09-23 10:57:14
我不是大佬,我才是蒟蒻/kk。
by 5_Lei @ 2022-09-23 10:58:41
@Error_Eric 数组版手动维护了,结构体直接用结构体赋值了
by 5_Lei @ 2022-09-23 10:59:51
结构体版的pushup因为重载了一下+运算符,忘了更新左右儿子,导致样例都过不去