首页 > 其他分享 >SS241007B. 逆序对(inverse)

SS241007B. 逆序对(inverse)

时间:2024-10-07 21:11:00浏览次数:6  
标签:inverse int SS241007B 端点 平面 左上角 矩形 逆序

SS241007B. 逆序对(inverse)

题意

给你一个长度为 \(n\) 的排列,你可以选择一对 \((i,j)\),交换 \(p_i,p_j\),或者不操作,使减少的逆序对个数最多,求最多减少几个逆序对。

思路

首先考虑交换 \(i,j\) 会对哪些部分的逆序对数量产生影响。不难发现,如果我们画一个二维平面,上面有 \(n\) 个点 \((i,p_i)\),那么交换 \((p_i,p_j)\) 减少的逆序对个数就是:设以 \((i,p_i)\) 为左上角,以 \((j,p_j)\) 为右下角的矩形内部覆盖了 \(s\) 个点,减少的逆序对个数就是 \(2s+1\)。

因此问题转化为对所有 \((i,j)\),求矩形内部覆盖的点数最多。

枚举所有左上角和右上角,然后二维前缀和计算矩形内部点数,时间复杂度是 \(O(n^2)\) 的。

通过敏锐的观察,可以发现不是所有点都有可能成为矩形的左上角或者右下角的。设点 \((k,p_k)\) 在点 \((i,p_i)\) 的右下方,那么左上角一定不会选择 \(k\),因为选择 \(i\) 必然更优,因此只有等于前缀最大值的 \(p_i\) 可能成为矩形左上角。同理可得,只有后缀最小值可能成为矩形右下角。长成图像就是所有可能的左上角,所有可能的右上角,都是单调递增的。

那么对于部分分的随机数据,发现随机条件下可能的左上角及右上角基本上都不超过 \(100\),因此直接枚举左上角、右上角,然后树状数组求一下矩形内部的点,就可以获得 \(70\) 分的高分了。

其实容易发现有一个很有前途的决策单调性,对于向右移动的矩形左上角,决策点(右下角)一定单调向右移动。因为左上端点向右上移动,所有决策(选择每个右下端点的矩形内点数)的变化量一定是越右边的越大。因此一个左边的决策点如果没有一个右边的决策点优,之后它会更加不优,可以直接扔掉它了。因此对于单调右上的左上角,决策点也是单调右上的。

但是题解的做法并没有利用这个决策单调性,场上我也没有想到很好地利用它的方法。

我们考虑转换思路,枚举每个点,处理这个点对哪些矩形有贡献。

发现这个点一定是对左上端点在这个点的左上方,右下端点在这个点的右下方,的矩形有贡献,也就是连续的一段左端点匹配连续的一段右端点。

一个十分巧妙的转化是,创建一个二维平面 \((左上端点编号,右下端点编号)\),叫做平面 2,刚刚那个二维平面叫做平面 1。然后每个平面 1 的点就相当于把平面 2 的一个矩形加 \(1\),最后问平面 2 最大的点的权值是多少。

由于我们不能把平面 2 建出来,所以我们离线所有对平面 2 的操作,然后扫描线,用线段树维护最大值即可。时间复杂度是 \(O(n \log n)\) 的。

code

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1e6+7;
namespace io {
	const int SIZE = (1 << 25) + 1;
	char ibuf[SIZE], *iS, *iT;
	char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[64];
	int f, qr;
	
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template <class I> inline void read (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); 
		x = f == -1 ? -x : x;
	}
	template <class I> inline void print (I x) {
		if (! x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[ ++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr -- ]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: print;
int n,p[N];
int lvec[N],rvec[N],ls[N],rs[N];
int cntl,cntr;
typedef pair<int,int> pii;
typedef vector<pii > vpii;
#define fi first 
#define se second
vpii opt[N];
int mx[N<<2],tag[N<<2];
int ans=0;
inline void maketag(int u,int val) {
    tag[u]+=val;
    mx[u]+=val;
}
inline void pushdown(int u) {if(tag[u]) maketag(u<<1,tag[u]),maketag(u<<1|1,tag[u]),tag[u]=0;}
inline void pushup(int u) {mx[u]=max(mx[u<<1],mx[u<<1|1]);}
void update(int u,int l,int r,int x,int val) {
    if(l>=x) {
        maketag(u,val);
        return;
    }
    pushdown(u);
    int mid=(l+r)>>1;
    if(x<=mid) update(u<<1,l,mid,x,val);
    update(u<<1|1,mid+1,r,x,val);
    pushup(u);
}
bool check() {
    rep(i,2,n) if(p[i]<p[i-1]) return 0;
    return 1;
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#else
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	#endif
    read(n);
    rep(i,1,n) read(p[i]);
    if(check()) {
        print(0);
        return 0;
    }
    int tmp=0;
    rep(i,1,n) {
    tmp=max(tmp,p[i]);
        if(p[i]==tmp) lvec[++cntl]=i,ls[cntl]=p[i];
    }
    tmp=N;
    per(i,n,1) {
        tmp=min(tmp,p[i]);
        if(p[i]==tmp) rvec[++cntr]=i,rs[cntr]=p[i];
    }
    reverse(rvec+1,rvec+cntr+1);
    reverse(rs+1,rs+cntr+1);
    int idl=1,idr=rvec[1]==1?1:0;
    rep(i,2,n-1) {
        if(i==lvec[idl+1]) idl++;
        if(i==rvec[idr+1]) idr++;
        int l=upper_bound(ls+1,ls+idl+1,p[i])-ls,r=lower_bound(rs+idr,rs+cntr+1,p[i])-rs-1;
        if(idr+1>r) continue;
        opt[idr+1].push_back({l,1}),opt[idr+1].push_back({idl+1,-1});
        opt[r+1].push_back({l,-1}),opt[r+1].push_back({idl+1,1});
    }
    rep(i,1,cntr) {
        for(pii op:opt[i]) {
            if(op.fi>=1&&op.fi<=cntl)
            update(1,1,cntl,op.fi,op.se);
        }
        ans=max(ans,mx[1]);
    }
    print(ans*2+1);
}

标签:inverse,int,SS241007B,端点,平面,左上角,矩形,逆序
From: https://www.cnblogs.com/liyixin0514/p/18450491

相关文章

  • LOJ6077 逆序对
    lojcwoi题意求逆序对数恰为\(m\)的长度为\(n\)的排列数。\(n,m\le10^5\)。solution\(n,m\le5000\)首先对于更小的数据可以直接状压。进一步观察,发现我们并不需要知道值之间的具体大小,只用相对大小就能计算贡献了。于是设\(f_{i,j}\)表示长为\(i\),逆序对数为......
  • 逆序对——树状数组
    逆序对题目描述猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中\(a_i>a_j\)且\(i<j\)......
  • C++——输入一个字符串,把其中的字符按逆序输出。如输入LIGHT,输出THGIL。用string方法
    没注释的源代码#include<iostream>#include<string.h>usingnamespacestd;intmain(){   stringa;   cout<<"请输入字符串a:";   cin>>a;   intk;   k=a.size();   for(inti=k-1;i>=0;i--)   {       cout<<a[i];......
  • DS堆栈--逆序输出(不使用STL栈)
    题目描述请编写堆栈操作的具体实现代码,实现字符串的逆序输出,需自行实现堆栈。输入一个字符串,按字符按输入顺序压入堆栈,然后根据堆栈后进先出的特点,做逆序输出输入第一行输入t,表示有t个测试实例第二起,每一行输入一个字符串,注意字符串不要包含空格字符串的输入可参考如下......
  • 算法-分治和逆序
    分治法(DivideandConquer)是一种重要的算法设计范式,它通过将复杂的问题分解成更小、更易于管理和解决的子问题,然后递归地解决这些子问题,最后将子问题的解合并以得到原问题的解。分治法通常用于排序、搜索、数学计算和优化等问题。分治法的核心思想可以概括为三个步骤:分......
  • 关于链表逆序的(递归方法)
    LinkNode*turnoff(LinkNode*head){head->next->next=head;head->next=NULL;returnhead;//这里我们需要返回新的头(head);}以上我们创建了一个简单但函数还不是递归的。上述我们不可以从头开始,要从尾巴开始;这个时候需要递归一下到最后一个节点。即:LinkNode*turnoff......
  • Imitating Language via Scalable Inverse Reinforcement Learning
    本文是LLM系列文章,针对《ImitatingLanguageviaScalableInverseReinforcementLearning》的翻译。通过可扩展的逆向强化学习模仿语言摘要1引言2方法3实验4相关工作5讨论6结论摘要大多数语言模型训练都建立在模仿学习的基础上。它涵盖了预训练、监......
  • 牛客 字符逆序,三角形判断(C)
    题目1(字符逆置)输入一个字符串str(可以输入空格),将其内容颠倒过来,并输出。题目链接:字符逆序__牛客网解体思路:我们可以自定义一个逆序函数Reverse。然后,我们将每个单词倒置过来。最后再输出整个字符串。其中,left代表左边,right代表右边,我们通过循环来控制交换的次数,每次循环......
  • 洛谷题单指南-分治与倍增-P1908 逆序对
    原题链接:https://www.luogu.com.cn/problem/P1908题意解读:求序列逆序对数。解题思路:1、暴力法对于每一个数,寻找后面有多少数比其小,或者采用冒泡排序,交换的次数即逆序对的个数,复杂度为O(n^2)2、归并排序法在归并排序过程中,会进行有序序列的合并,设两部分连续的有序序列为a[s1,......
  • python怎么逆序
    python中字符串数组如何逆序排列?下面给大家介绍几种方法:1、数组倒序:原始元素的倒序排列(1)切片>>> arr = [1,2,3,4,3,4]>>> print (arr[::-1])[4, 3, 4, 3, 2, 1](2)reverse()>>> arr = [1,2,3,4,3,4]>>> arr.reverse()>>> print (arr)[4, 3, 4, ......