QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#158684#7108. Couleurucup-team1321#AC ✓2481ms34252kbC++144.3kb2023-09-02 16:51:152023-09-02 16:51:16

Judging History

你现在查看的是最新测评结果

  • [2023-09-02 16:51:16]
  • 评测
  • 测评结果：AC
  • 用时：2481ms
  • 内存：34252kb
查看
  • [2023-09-02 16:51:15]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#include<tuple>
using namespace std;
const int N=100005;
int n;
int a[N];
long long p[N],z[N];
struct Chairman_Tree
{
    struct Node
    {
        int ls,rs;
        int sum;
    }tree[N<<5];
    int rt[N],tot;
    int new_node()
    {
        int now=++tot;
        tree[now].ls=tree[now].rs=0;
        tree[now].sum=0;
        return now;
    }
    void clear()
    {
        tot=0;
        for(int i=1;i<=n;i++)
            rt[i]=0;
        return;
    }
    void push_up(int i)
    {
        tree[i].sum=tree[tree[i].ls].sum+tree[tree[i].rs].sum;
        return;
    }
    void build(int &i,int l,int r)
    {
        i=new_node();
        if(l==r)
        {
            tree[i].sum=0;
            return;
        }
        int mid=(l+r)/2;
        build(tree[i].ls,l,mid);
        build(tree[i].rs,mid+1,r);
        return;
    }
    int modify(int i,int l,int r,int u,int v)
    {
        int now=++tot;
        tree[now]=tree[i];
        if(l==r)
        {
            tree[now].sum+=v;
            return now;
        }
        int mid=(l+r)/2;
        if(u<=mid) tree[now].ls=modify(tree[i].ls,l,mid,u,v);
        else tree[now].rs=modify(tree[i].rs,mid+1,r,u,v);
        push_up(now);
        return now;
    }
    int query(int i,int l,int r,int L,int R)
    {
        if(L>R) return 0;
        if(!i) return 0;
        if(L>R) return 0;
        if(L<=l&&r<=R) return tree[i].sum;
        int mid=(l+r)/2;
        int res=0;
        if(L<=mid) res+=query(tree[i].ls,l,mid,L,R);
        if(R>mid) res+=query(tree[i].rs,mid+1,r,L,R);
        return res;
    }
}T;
set<tuple<int,int,long long>>seg;
multiset<long long,greater<int>>S;
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&p[i]);
    T.clear();
    T.build(T.rt[0],1,n);
    for(int i=1;i<=n;i++)
        T.rt[i]=T.modify(T.rt[i-1],1,n,a[i],1);
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans+=T.query(T.rt[i-1],1,n,a[i]+1,n);
    z[0]=ans;
    seg.clear();
    seg.insert(make_tuple(1,n,ans));
    S.insert(ans);
    for(int i=1;i<=n;i++)
    {
        p[i]^=z[i-1];
        // cerr<<"now"<<i<<" "<<p[i]<<"\n";
        set<tuple<int,int,long long>>::iterator it=seg.lower_bound(make_tuple(p[i],n+1,0));
        it--;
        auto [l1,r2,sum]=*it;
        S.erase(S.lower_bound(sum));
        seg.erase(it);
        int r1=p[i]-1,l2=p[i]+1;
        if(l1<=r1) sum-=T.query(T.rt[r1],1,n,a[p[i]]+1,n)-T.query(T.rt[l1-1],1,n,a[p[i]]+1,n);
        if(l2<=r2) sum-=T.query(T.rt[r2],1,n,1,a[p[i]]-1)-T.query(T.rt[l2-1],1,n,1,a[p[i]]-1);
        // cerr<<"del"<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<sum<<"\n";
        long long res1=0,res2=0;
        if(r2-l2+1<r1-l1+1)
        {
            if(l2<=r2)
            {
                if(l1<=r1)
                {
                    for(int i=l2;i<=r2;i++)
                        sum-=T.query(T.rt[r1],1,n,a[i]+1,n)-T.query(T.rt[l1-1],1,n,a[i]+1,n);
                }
                for(int i=l2;i<=r2;i++)
                    res2+=T.query(T.rt[i-1],1,n,a[i]+1,n)-T.query(T.rt[l2-1],1,n,a[i]+1,n);
            }
            res1=sum-res2;
        }
        else
        {
            if(l1<=r1)
            {
                if(l2<=r2)
                {
                    for(int i=l1;i<=r1;i++)
                        sum-=T.query(T.rt[r2],1,n,1,a[i]-1)-T.query(T.rt[l2-1],1,n,1,a[i]-1);
                }
                for(int i=l1;i<=r1;i++)
                    res1+=T.query(T.rt[i-1],1,n,a[i]+1,n)-T.query(T.rt[l1-1],1,n,a[i]+1,n);
            }
            res2=sum-res1;
        }
        if(l1<=r1) seg.insert(make_tuple(l1,r1,res1)),S.insert(res1);
        if(l2<=r2) seg.insert(make_tuple(l2,r2,res2)),S.insert(res2);
        if(!S.empty()) z[i]=*S.begin();
        // cerr<<"res"<<i<<" "<<res1<<" "<<res2<<"\n";
    }
    for(int i=0;i<n;i++)
        if(i<n-1) printf("%lld ",z[i]);
        else printf("%lld\n",z[i]);
    return;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        solve();
    return 0;
}

/*
3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10
*/
源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5924kb

input:

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

output:

7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2481ms
memory: 34252kb

input:

11116
10
10 5 10 3 6 4 8 5 9 8
31 27 24 11 12 3 0 2 3 1
10
8 2 7 2 8 10 1 10 9 10
6 5 2 13 2 1 0 1 3 1
10
7 10 7 6 1 3 10 6 7 9
21 18 10 1 6 5 4 8 9 10
10
2 10 4 8 8 5 7 2 6 7
20 10 9 1 15 0 4 2 9 7
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
6 3 5 2 7 10 9 1 4 8
10
1 10 1 3...

output:

21 18 16 12 10 6 4 1 1 0
12 12 10 10 4 4 4 2 1 0
20 16 9 5 3 3 3 0 0 0
22 14 8 8 5 5 2 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
19 12 7 4 4 2 2 1 0 0
20 18 8 3 1 1 0 0 0 0
45 21 21 10 3 3 3 0 0 0
17 11 8 2 1 1 1 0 0 0
13 4 1 0 0 0 0 0 0 0
29 27 22 15 9 7 4 3 1 0
26 16 9 2 1 1 1 1 1 0
0 0 0 0 0 ...

result:

ok 11116 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-03 04:53:05 | 开源项目