WA30的可能解决方法

P2839 [国家集训队] middle

hejianxing @ 2023-12-22 21:20:16

其它帖子说离散化不要去重。

其实去重也是可以的，只需要记录 vr[x] 表示将 \ge x 的位置全部标 1 的根，查询的时候就查询 vr[x] 为根的树。

不过要注意 vr[x] 的更新顺序。

可以这么实现：

bdtr(root[1], 1, n);
    for (int i = 2; i <= n + 1; i++) {
        arr h = pq.top();
        pq.pop();
        if (!vr[h.v]) vr[h.v] = root[i - 1];
        update(root[i - 1], root[i], 1, n, h.id);
    }

by cxlian25 @ 2024-01-30 17:46:30

@hejianxing 可否请您看一下我的帖子的30分的错误在哪吗？就在本题第一个帖子

by cxlian25 @ 2024-01-30 18:18:32

@hejianxing 已经解决了，不过我虽然非常相信您说的话，可是为什么我的代码仅仅是注释了104行就解决了所有问题？

//#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:19:18

@hejianxing 104行：

len=unique(b+1,b+1+n)-b-1;

by cxlian25 @ 2024-01-30 18:28:47

@hejianxing 我想我知道了，我可持久化的是线段树不是权值线段树

by hejianxing @ 2024-01-31 08:51:10

@cxlian25 问题在这：

你的：

    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;
    }

改成：

    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 代码：

//#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 Atwenty @ 2024-02-20 16:27:08

但是好像把您改的这版代码的104行取消注释就又变成wa30了T_T，想问问到底是应该将>=期望值的位置标记为1，还是将>期望值的位置标记为1呢？

by 普通的名字 @ 2024-02-27 20:17:20

@hejianxing 骚鸡tql

by hejianxing @ 2024-02-28 11:22:52

@Atwenty

\ge x$ 的位置标为 $1

by hejianxing @ 2024-02-28 11:31:19

@Atwenty

这次过了。

主席树的范围还是 n。因为主席树的叶子节点就是原数组的位置，这个位置的值 \ge x 就标为 1，离散化的是数组的值，但是数组的长度还是 n。

//#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
*/
|