Couleur(启发式 + 主席树)（终于补坑了）

ZOJ Problem Set - 4053

Couleur

Time Limit: 6 Seconds Memory Limit: 131072 KB

DreamGrid has an array of integers. On this array he can perform the following operation: choose an element that was not previously chosen and mark it as unavailable. DreamGrid would like to perform exactly operations until all the elements are marked.

DreamGrid defines the cost of a subarray as the number of inversions in the subarray. Before performing an operation, DreamGrid would like to know the maximum cost of a subarray that doesn't contain any unavailable elements.

Recall that a subarray is a contiguous subpart of the original array where . An inversion in a subarray is a pair of indices such that the inequality holds.

Input

There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:

The first line contains a single integer -- the length of the array.

The second line contains the values of the array .

The third line contains a permutation , representing the indices of the elements chosen for the operations in order.

Note that the permutation is encrypted and you can get the real permutation using the following method: Let be the answer before the -th operation. The actual index of the -th operation is where is bitwise exclusive or operator.

It is guaranteed that the sum of all does not exceed .

Output

For each test case, output integers in a single line seperated by one space, where is the answer before the -th operation.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Sample Input

354 3 1 1 15 4 5 3 1109 7 1 4 7 8 5 7 4 821 8 15 5 9 2 4 5 10 6154 8 8 1 12 1 10 14 7 14 2 9 13 10 337 19 23 15 7 2 10 15 2 13 4 5 8 7 10

Sample Output

7 0 0 0 020 11 7 2 0 0 0 0 0 042 31 21 14 14 4 1 1 1 0 0 0 0 0 0

Hint

The decoded permutation of each test case is , and

Author: LIN, Xi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online

题目大意给一个序列然后按照一定顺序删掉一些数字使得序列不连续要让我们去找出逆序数最大的连续序列输出这个连续序列的逆序对数
本蒟蒻在做这个题目的时候用的set维护的最大的逆序数
QAQ 一直都不对这个题目要用muliset 维护啊 qaq qaq qaq qaq qaq
有关这个逆序数的关系传递值得思考

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
const int maxn = 1e5+7;
#define ll long long
struct tree{int l,r,sum;}T[maxn*40];
int a[maxn],p[maxn],root[maxn],N;ll z[maxn],big[maxn],cnt;
void update(int &x,int y,int l,int r,int pos)
{
    T[++cnt]=T[y],x=cnt,T[x].sum++;
    if(l==r)return;
    int m=(l+r)>>1;
    if(pos<=m)update(T[x].l,T[y].l,l,m,pos);
    else update(T[x].r,T[y].r,m+1,r,pos);
}
ll findbig(int x,int y,int l,int r,int pos)
{
    if(l==r)return 0;
    int m=(l+r)>>1;
    if(pos<=m)return findbig(T[x].l,T[y].l,l,m,pos)+T[T[y].r].sum-T[T[x].r].sum;
    return findbig(T[x].r,T[y].r,m+1,r,pos);
}
ll findsmall(int x,int y,int l,int r,int pos)
{
    if(l==r)return 0;
    int m=(l+r)>>1;
    if(pos<=m)return findsmall(T[x].l,T[y].l,l,m,pos);
    return findsmall(T[x].r,T[y].r,m+1,r,pos)+T[T[y].l].sum-T[T[x].l].sum;
}
set<int>se;
multiset<ll>Maxinv;
set<int>::iterator it;
ll delet(int x)
{

    se.insert(x);it=se.find(x);
    int l=*(--it) +1;++it;int r=*(++it) -1;
    if(big[r])Maxinv.erase(Maxinv.find(big[r]));
    ll invl=0,invr=0,t=0;
    if(x-l<r-x)
    {
        for(int i=l;i<x;i++)
        {
            invl+=findbig(root[l-1],root[i],1,N,a[i]);
            t+=findsmall(root[i],root[r],1,N,a[i]);
        }
        invr=big[r]-t-findsmall(root[x],root[r],1,N,a[x]);
    }else{
        for(int i=x+1;i<=r;i++)
        {
            invr+=findsmall(root[i],root[r],1,N,a[i]);
            t+=findbig(root[l-1],root[i],1,N,a[i]);
        }
        invl=big[r]-t-findbig(root[l-1],root[x],1,N,a[x]);
    }
    big[x-1]=invl;big[r]=invr;
    if(invl)Maxinv.insert(invl);if(invr)Maxinv.insert(invr);
    multiset<ll>::iterator its=Maxinv.end();
    return *(--its);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        se.clear();cnt=0;Maxinv.clear();Maxinv.insert(0);
        scanf("%d",&N);se.insert(0),se.insert(N+1);
        for(int i=1;i<=N;i++)scanf("%d",a+i);
        for(int i=1;i<=N;i++)scanf("%d",p+i);
        for(int i=1;i<=N;i++)update(root[i],root[i-1],1,N,a[i]);
        for(int i=1;i<=N;i++)big[i]=big[i-1]+findbig(root[0],root[i],1,N,a[i]);
        z[1]=big[N];Maxinv.insert(z[1]);
        for(int i=1;i<N;i++)z[i+1]=delet(z[i]^p[i]);
        for(int i=1;i<N;i++)printf("%lld ",z[i]);
        printf("%lld
",z[N]);
    }
    return 0;
}

View Code