@[hejianxing](/user/566238) 可否请您看一下我的帖子的30分的错误在哪吗？就在本题第一个帖子
by cxlian25 @ 2024-01-30 17:46:30
@[hejianxing](/user/566238) 已经解决了，不过我虽然非常相信您说的话，可是为什么我的代码仅仅是注释了104行就解决了所有问题？
```cpp
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<cmath>
#include<queue>
#include<map>
#include<cstring>
#include<vector>
#include<set>
#define ll long long
#define lx (x<<1)
//#define endl '\n'
#define rx (x<<1|1)
#define db double
#define pb push_back
#define mp make_pair
#define pa pair<int,int>
#define mid ((l+r)>>1)
#define mem(a) memset(a,0,sizeof(a))
#define memf(a) memset(a,127,sizeof(a))//浮点，int数最大
#define memm(a) memset(a,0x3f,sizeof(a))//1e9
#define memn(a) memset(a,0xcf,sizeof(a))//int最小
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ct(a) (__builtin_popcount(a))
#define lowbit(i) (i&(-i))
using namespace std;
const int N=1e5+7,M=1e6,p=1000000007;
const double eps=1e-9,pi=acos(-1.0);
int tt;
int n,m,cnt=0,len=0;
int a[N],b[N],id=0,q[9];
struct tree{
int l,r;
int mxl,mxr,sum;
}st[N<<5];
vector<int>v[N];
int root[N];
int build(int l,int r){
int now=++cnt;
if(l<r){
st[now].l=build(l,mid);
st[now].r=build(mid+1,r);
}
else{
st[now].mxl=st[now].mxr=1;
st[now].sum=1;
return now;
}
st[now].sum=st[st[now].l].sum+st[st[now].r].sum;
st[now].mxl=max(st[st[now].l].mxl,st[st[now].l].sum+st[st[now].r].mxl);
st[now].mxr=max(st[st[now].r].mxr,st[st[now].r].sum+st[st[now].l].mxr);
return now;
}
int add(int pre,int l,int r,int x){
int now=++cnt;
if(l==r){
st[now].mxl=st[now].mxr=-1;
st[now].sum=-1;
return now;
}
st[now].l=st[pre].l;
st[now].r=st[pre].r;
if(x<=mid)st[now].l=add(st[pre].l,l,mid,x);
else st[now].r=add(st[pre].r,mid+1,r,x);
st[now].sum=st[st[now].l].sum+st[st[now].r].sum;
st[now].mxl=max(st[st[now].l].mxl,st[st[now].l].sum+st[st[now].r].mxl);
st[now].mxr=max(st[st[now].r].mxr,st[st[now].r].sum+st[st[now].l].mxr);
return now;
}
tree qry1(int x,int l,int r,int sl,int sr){
tree now;now.sum=-10000000;
if(sr<l||sl>r)return now;
if(sl<=l&&sr>=r)return st[x];
tree left=qry1(st[x].l,l,mid,sl,sr);
tree right=qry1(st[x].r,mid+1,r,sl,sr);
if(left.sum==-10000000&&right.sum==-10000000)return now;
if(left.sum==-10000000)return right;
if(right.sum==-10000000)return left;
now.mxl=max(left.mxl,left.sum+right.mxl);
now.mxr=max(right.mxr,right.sum+left.mxr);
now.sum=left.sum+right.sum;
return now;
}
bool check(int w){
int sum=0;
if(q[2]+1<=q[3]-1)sum=sum+qry1(root[w],1,len,q[2]+1,q[3]-1).sum;
sum=sum+qry1(root[w],1,len,q[1],q[2]).mxr;
sum=sum+qry1(root[w],1,len,q[3],q[4]).mxl;
return sum>=0;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
len=n;
// len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+len,a[i])-b;
v[a[i]].pb(i);
}
root[1]=build(1,len);
for(int i=2;i<=len;i++){
int y=root[i-1];
for(auto x:v[i-1]){
y=add(y,1,len,x);
}
root[i]=y;
}
scanf("%d",&m);
int tmp=0;
while(m--){
for(int i=1;i<=4;i++){
scanf("%d",&q[i]);
q[i]=(q[i]+tmp)%n+1;
}
sort(q+1,q+1+4);
int l=1,r=len;
while(l<=r){
if(check(mid))l=mid+1;
else r=mid-1;
}
tmp=b[r];
printf("%d\n",tmp);
}
}
/*
300000 2 30
*/
signed main(){
// IOS;
// cin>>tt;
// scanf("%d",&tt);
tt=1;
while(tt--){
solve();
// puts("");
}
return 0;
}
/*
1
1 2 3 4 5
1 2 2 3 3
*/
```
by cxlian25 @ 2024-01-30 18:18:32
@[hejianxing](/user/566238) 104行：
```cpp
len=unique(b+1,b+1+n)-b-1;
```
by cxlian25 @ 2024-01-30 18:19:18
@[hejianxing](/user/566238) 我想我知道了，我可持久化的是线段树不是权值线段树
by cxlian25 @ 2024-01-30 18:28:47
@[cxlian25](/user/836104) 问题在这：
你的：
```cpp
root[1]=build(1,len);
for(int i=2;i<=len;i++){
int y=root[i-1];
for(auto x:v[i-1]){
y=add(y,1,len,x);
}
root[i]=y;
}
```
改成：
```cpp
root[0]=build(1,len);
for(int i=1;i<=len;i++){
int y=root[i-1];
for(auto x:v[i-1]){
y=add(y,1,len,x);
}
root[i]=y;
}
```
应该将初始的版本设为 $0$，这样才能在版本为 $i$ 时更新第 $i$ 大的。
AC 代码：
```cpp
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<cmath>
#include<queue>
#include<map>
#include<cstring>
#include<vector>
#include<set>
#define ll long long
#define lx (x<<1)
//#define endl '\n'
#define rx (x<<1|1)
#define db double
#define pb push_back
#define mp make_pair
#define pa pair<int,int>
#define mid ((l+r)>>1)
#define mem(a) memset(a,0,sizeof(a))
#define memf(a) memset(a,127,sizeof(a))//浮点，int数最大
#define memm(a) memset(a,0x3f,sizeof(a))//1e9
#define memn(a) memset(a,0xcf,sizeof(a))//int最小
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ct(a) (__builtin_popcount(a))
#define lowbit(i) (i&(-i))
using namespace std;
const int N=1e5+7,M=1e6,p=1000000007;
const double eps=1e-9,pi=acos(-1.0);
int tt;
int n,m,cnt=0,len=0;
int a[N],b[N],id=0,q[9];
struct tree{
int l,r;
int mxl,mxr,sum;
}st[N<<5];
vector<int>v[N];
int root[N];
int build(int l,int r){
int now=++cnt;
if(l<r){
st[now].l=build(l,mid);
st[now].r=build(mid+1,r);
}
else{
st[now].mxl=st[now].mxr=1;
st[now].sum=1;
return now;
}
st[now].sum=st[st[now].l].sum+st[st[now].r].sum;
st[now].mxl=max(st[st[now].l].mxl,st[st[now].l].sum+st[st[now].r].mxl);
st[now].mxr=max(st[st[now].r].mxr,st[st[now].r].sum+st[st[now].l].mxr);
return now;
}
int add(int pre,int l,int r,int x){
int now=++cnt;
if(l==r){
st[now].mxl=st[now].mxr=-1;
st[now].sum=-1;
return now;
}
st[now].l=st[pre].l;
st[now].r=st[pre].r;
if(x<=mid)st[now].l=add(st[pre].l,l,mid,x);
else st[now].r=add(st[pre].r,mid+1,r,x);
st[now].sum=st[st[now].l].sum+st[st[now].r].sum;
st[now].mxl=max(st[st[now].l].mxl,st[st[now].l].sum+st[st[now].r].mxl);
st[now].mxr=max(st[st[now].r].mxr,st[st[now].r].sum+st[st[now].l].mxr);
return now;
}
tree qry1(int x,int l,int r,int sl,int sr){
tree now;now.sum=-10000000;
if(sr<l||sl>r)return now;
if(sl<=l&&sr>=r)return st[x];
tree left=qry1(st[x].l,l,mid,sl,sr);
tree right=qry1(st[x].r,mid+1,r,sl,sr);
if(left.sum==-10000000&&right.sum==-10000000)return now;
if(left.sum==-10000000)return right;
if(right.sum==-10000000)return left;
now.mxl=max(left.mxl,left.sum+right.mxl);
now.mxr=max(right.mxr,right.sum+left.mxr);
now.sum=left.sum+right.sum;
return now;
}
bool check(int w){
int sum=0;
if(q[2]+1<=q[3]-1)sum=sum+qry1(root[w],1,len,q[2]+1,q[3]-1).sum;
sum=sum+qry1(root[w],1,len,q[1],q[2]).mxr;
sum=sum+qry1(root[w],1,len,q[3],q[4]).mxl;
return sum>=0;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
len=n;
// len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+len,a[i])-b;
v[a[i]].pb(i);
}
root[0]=build(1,len);
for(int i=1;i<=len;i++){
int y=root[i-1];
for(auto x:v[i-1]){
y=add(y,1,len,x);
}
root[i]=y;
}
scanf("%d",&m);
int tmp=0;
while(m--){
for(int i=1;i<=4;i++){
scanf("%d",&q[i]);
q[i]=(q[i]+tmp)%n+1;
}
sort(q+1,q+1+4);
int l=1,r=len;
while(l<=r){
if(check(mid))l=mid+1;
else r=mid-1;
}
tmp=b[r];
printf("%d\n",tmp);
}
}
/*
300000 2 30
*/
signed main(){
// IOS;
// cin>>tt;
// scanf("%d",&tt);
tt=1;
while(tt--){
solve();
// puts("");
}
return 0;
}
/*
1
1 2 3 4 5
1 2 2 3 3
*/
```
by hejianxing @ 2024-01-31 08:51:10
但是好像把您改的这版代码的104行取消注释就又变成wa30了T_T，想问问到底是应该将>=期望值的位置标记为1，还是将>期望值的位置标记为1呢？
by Atwenty @ 2024-02-20 16:27:08
@[hejianxing](/user/566238) 骚鸡tql
by 普通的名字 @ 2024-02-27 20:17:20
@[Atwenty](/user/258071)
$\ge x$ 的位置标为 $1$
by hejianxing @ 2024-02-28 11:22:52
@[Atwenty](/user/258071)
这次过了。
主席树的范围还是 $n$。因为主席树的叶子节点就是原数组的位置，这个位置的值 $\ge x$ 就标为 $1$，离散化的是数组的值，但是数组的长度还是 $n$。
```cpp
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<cmath>
#include<queue>
#include<map>
#include<cstring>
#include<vector>
#include<set>
#define ll long long
#define lx (x<<1)
//#define endl '\n'
#define rx (x<<1|1)
#define db double
#define pb push_back
#define mp make_pair
#define pa pair<int,int>
#define mid ((l+r)>>1)
#define mem(a) memset(a,0,sizeof(a))
#define memf(a) memset(a,127,sizeof(a))//浮点，int数最大
#define memm(a) memset(a,0x3f,sizeof(a))//1e9
#define memn(a) memset(a,0xcf,sizeof(a))//int最小
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ct(a) (__builtin_popcount(a))
#define lowbit(i) (i&(-i))
using namespace std;
const int N=1e5+7,M=1e6,p=1000000007;
const double eps=1e-9,pi=acos(-1.0);
int tt;
int n,m,cnt=0,len=0;
int a[N],b[N],id=0,q[9];
struct tree{
int l,r;
int mxl,mxr,sum;
}st[N<<5];
vector<int>v[N];
int root[N];
int build(int l,int r){
int now=++cnt;
if(l<r){
st[now].l=build(l,mid);
st[now].r=build(mid+1,r);
}
else{
st[now].mxl=st[now].mxr=1;
st[now].sum=1;
return now;
}
st[now].sum=st[st[now].l].sum+st[st[now].r].sum;
st[now].mxl=max(st[st[now].l].mxl,st[st[now].l].sum+st[st[now].r].mxl);
st[now].mxr=max(st[st[now].r].mxr,st[st[now].r].sum+st[st[now].l].mxr);
return now;
}
int add(int pre,int l,int r,int x){
int now=++cnt;
if(l==r){
st[now].mxl=st[now].mxr=-1;
st[now].sum=-1;
return now;
}
st[now].l=st[pre].l;
st[now].r=st[pre].r;
if(x<=mid)st[now].l=add(st[pre].l,l,mid,x);
else st[now].r=add(st[pre].r,mid+1,r,x);
st[now].sum=st[st[now].l].sum+st[st[now].r].sum;
st[now].mxl=max(st[st[now].l].mxl,st[st[now].l].sum+st[st[now].r].mxl);
st[now].mxr=max(st[st[now].r].mxr,st[st[now].r].sum+st[st[now].l].mxr);
return now;
}
tree qry1(int x,int l,int r,int sl,int sr){
tree now;now.sum=-10000000;
if(sr<l||sl>r)return now;
if(sl<=l&&sr>=r)return st[x];
tree left=qry1(st[x].l,l,mid,sl,sr);
tree right=qry1(st[x].r,mid+1,r,sl,sr);
if(left.sum==-10000000&&right.sum==-10000000)return now;
if(left.sum==-10000000)return right;
if(right.sum==-10000000)return left;
now.mxl=max(left.mxl,left.sum+right.mxl);
now.mxr=max(right.mxr,right.sum+left.mxr);
now.sum=left.sum+right.sum;
return now;
}
bool check(int w){
int sum=0;
if(q[2]+1<=q[3]-1)sum=sum+qry1(root[w],1,n,q[2]+1,q[3]-1).sum;
sum=sum+qry1(root[w],1,n,q[1],q[2]).mxr;
sum=sum+qry1(root[w],1,n,q[3],q[4]).mxl;
return sum>=0;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
len=n;
len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+len,a[i])-b;
v[a[i]].pb(i);
}
root[0]=build(1,n);
for(int i=1;i<=len;i++){
int y=root[i-1];
for(auto x:v[i-1]){
y=add(y,1,n,x);
}
root[i]=y;
}
scanf("%d",&m);
int tmp=0;
while(m--){
for(int i=1;i<=4;i++){
scanf("%d",&q[i]);
q[i]=(q[i]+tmp)%n+1;
}
sort(q+1,q+1+4);
int l=1,r=len;
while(l<=r){
if(check(mid))l=mid+1;
else r=mid-1;
}
tmp=b[r];
printf("%d\n",tmp);
}
}
/*
300000 2 30
*/
signed main(){
// IOS;
// cin>>tt;
// scanf("%d",&tt);
tt=1;
while(tt--){
solve();
// puts("");
}
return 0;
}
/*
1
1 2 3 4 5
1 2 2 3 3
*/
```
by hejianxing @ 2024-02-28 11:31:19