首页 > 其他分享 >E. Permutation Sorting

E. Permutation Sorting

时间:2024-07-11 10:30:02浏览次数:16  
标签:cnt Sorting int memset Permutation 区间 sizeof now

原题链接

题解

对于数 \(i\) 来说,如果其当前位置到最终位置上,有 \(k\) 个数不在最终位置,那么数 \(i\) 至少要走 \(k\) 次
如果这 \(k\) 个数里,有 \(m\) 个在数 \(i\) 回到最终位置时,提前回到了最终位置,那么数 \(i\) 要走 \(k-m\) 次

具象化就是一个一个的区间(起点为当前位置,终点为最终位置),数 \(i\) 要走的步数,就是其区间内不匹配的个数减去完全包裹住的小区间个数

由于环状,所以还要拆环成链
如何统计大区间内有多少完全包裹的小区间?
我么倒叙遍历,如果一个区间的左端点出现,那就令其右端点呈现
然后统计区间和,有几个右端点呈现

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;

int n;
int ans[1000006];
int tree[2000005]={0};
int cnt[2000005]={0};
int a[200005];

void update(int now)
{
    while(now<=2*n)
    {
        tree[now]++;
        now+=lowbit(now);
    }
}

int query(int now)
{
    int res=0;
    while(now)
    {
        res+=tree[now];
        now-=lowbit(now);
    }
    return res;
}

int r[2000006];

void solve()
{
    cin>>n;

    memset(tree, 0, sizeof(int) * (2*n + 1));
    memset(cnt, 0, sizeof(int) * (2*n + 1));
    memset(r, 0, sizeof(int) * (2*n + 1));
    memset(ans, 0, sizeof(int) * (n + 1));

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];

        if(a[i]>i)
        {
            r[i]=a[i];
            r[i+n]=a[i]+n;
        }
        else if(a[i]<i) r[i]=a[i]+n;
    }

    cnt[2*n+1]=0;
    for(int i=2*n;i>=1;i--)
    {
        cnt[i]=cnt[i+1]+(a[(i-1)%n+1]!=(i-1)%n+1);
    }

    for(int i=2*n;i>=1;i--)
    {
        if(r[i])
        {
            int now=(r[i]-1)%n+1;
            ans[now]=cnt[i+1]-cnt[r[i]+1]-(query(r[i])-query(i));
            update(r[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

标签:cnt,Sorting,int,memset,Permutation,区间,sizeof,now
From: https://www.cnblogs.com/pure4knowledge/p/18295524

相关文章

  • Yet Another Permutation Constructive
    这道题目不用写,因为必须要求用kotlin语言讲一下我做这道题目的过程我最开始正着想,如果\(k\)比较大的话,我们就想一次删的数少一点,所以考虑一次操作有哪些数被保留,于是我们发现,原序列的极大值点会被保留,于是一次操作被保留的数最多的情况就是如下的波浪形:然后我们就发现正着想很......
  • [题解]CF1741B Funny Permutation
    思路简单构造题,我们可以分为三种情况进行构造。\(n=3\)时,一定无解,输出-1。(你可以试试)\(n\bmod2=1\wedgen\neq3\)时,我们直接先输出\(n,n-1\),然后顺序输出即可。证明:令\(a\)为最后构造出的序列。那么,\(a_1=n,a_2=n-1,a_i=i-2(3\leqi\leq......
  • [题解]CF622D Optimal Number Permutation
    思路首先考虑答案下界,因为\((n-i)\)和\(|d_i+i-n|\)均大于等于\(0\),所以它们相乘一定大于等于\(0\)。于是考虑能不能构造出结果为\(0\)。显然当\(i=n\)时,无论\(d_i\)的值是什么,式子的结果为\(0\)。因此只需要考虑\(i\in[1,n)\)的情况。因为要使结果为......
  • D. Prefix Permutation Sums
    原题链接题解1.缺少一个前缀和,缺少在哪了?如果缺少在\(i<n\)的地方,则会出现一个两个数之和,即缺少两个数否则会只缺少一个数2.两个数之和可能大于\(n\),也可能不3.虽然\(a_i\)达到了\(1e18\)但是\(n\leq2e5\),所以可以用数组记录出现的数code#include<bits/stdc++.......
  • WPF CollectionViewSource.GetDefaultView ICollectionViewLiveShaping IsLiveSorting
    <Windowx:Class="WpfApp147.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.microsoft......
  • Topcoder SRM592-Div1-Lv2 LittleElephantAndPermutationDiv1
    题意设\(A,B\)为两个长为\(n\(\leq50)\)的排列,定义操作\(F(A,B)=\sum\limits_{i=1}^{n}\max(A_i,B_i)\),给定\(n,k\),求有多少种有序对\((A,B)\)满足\(F(A,B)\geqk\),答案模\(10^9+7\)。思路首先还是用经典的思路将无序转为无序,我们假定\(A\)是有序的即\(A={1,2,3,......
  • Learning Latent Permutations with Gumbel-Sinkhorn Networks
    目录概SinkHornoperatorMeanG.E.,BelangerD.,LindermanC.andSnoekJ.Learninglatentpermutationswithgumbel-sinkhornnetworks.ICLR,2018.概本文提出了一种自动学习permutations的方法.SinkHornoperatorSinkHornoperator的操作流程如下:\[S^{0}(......
  • CF1089I Interval-Free Permutations
    标签:析合树析合树就是用来处理这一种值域连续段的问题的。OI-wiki上对于析合树的讲解。我们回顾一下题目,要求不存在长度为\([2,n-1]\)之间的连续段,换句话说,就是根节点下恰有\(n-1\)个节点,且没有任何一个字段是题目中要求的连续段。我们记这样的答案为\(A_n\)也就......
  • UVA11922 Permutation Transformer 题解
    题目传送门前置知识无旋treap解法与luoguP3391【模板】文艺平衡树不同的是本题翻转后需要放到整个序列的末尾。由于需要翻转后放到末尾,故无旋Treap在维护文艺平衡树的过程中合并时跳着合并即可。代码#include<bits/stdc++.h>usingnamespacestd;#definelllong......
  • CF1909I Short Permutation Problem 题解
    这是一道*1900的黑。考虑枚举\(m\),将\(<\fracm2\)和\(\ge\fracm2\)的数分开讨论。考虑相邻两个数\(a,b\(a>b)\)分别在\(\fracm2\)的两侧,则有\(b\gem-a\)。考虑将所有数按某种方法从小到大排序,以\(\min(x,m-x)\)为第一关键字,\(-x\)为第二关键字,则排列中......