精华内容
下载资源
问答
  • 给一个长度为 nnn 的排列 aia_iai​,把它划分为若干段,每划分一段有 XXX 的代价,划分完后段内需要排序,代价为区间逆序对个数。求最小总代价。 n≤300000,1≤X≤109n\le 300000,1\le X\le 10^9n≤300000,1≤X≤...

    题目描述

    给一个长度为 nn 的排列 aia_i,把它划分为若干段,每划分一段有 XX 的代价,划分完后段内需要排序,代价为区间逆序对个数。求最小总代价。

    n300000,1X109n\le 300000,1\le X\le 10^9

    时限 5s.

    题目分析

    暴力 O(n2)O(n^2) DP:fi=fj+inversion_pair(j+1,i)f_i=f_j+inversion\_pair(j+1,i)

    经验丰富的OI选手可以立马猜测决策单调性,证明也很简单,代价函数在区间越大的情况下增长越快,当在 ii 处决策点 kk 比决策点 jj 劣时(k<jk<j),在 i>ii'>i 处也必然比后者劣。

    然而二分维护栈的做法需要在线求出区间逆序对个数,这是个 nnn\sqrt n 的问题,还需要乘个 log\log,300000显然跑不动。

    而分治做法则可以与莫队类似,用树状数组维护有多少个数小于 xx,当决策点移动时添加/删除区间前端/后端的点,根据分治的过程可以看出这样区间移动的次数是 O(nlogn)O(n\log n) 级别的。

    但是分治要建立在决策点区间的 ff 都已知的前提下,于是需要在外层再套一个 cdq 分治。
    总复杂度 O(nlog3n)O(n\log^3n),但是常数很小。

    如果要严格写,每次撤销略麻烦,经过实际测试不如直接用类似莫队的写法快,即如果当前区间与询问区间不符则移动,非常好写。

    Code:

    #include<bits/stdc++.h>
    #define maxn 300005
    #define LL long long
    using namespace std;
    const LL inf = 0x3f3f3f3f3f3f3f3fll;
    int n,X,a[maxn];
    LL f[maxn];
    int arr[maxn];
    void upd(int i,int v){for(;i<=n;i+=i&-i) arr[i]+=v;}
    int qsum(int i){int s=0;for(;i;i-=i&-i) s+=arr[i];return s;}
    LL ask(int x,int y){
    	static int l=1,r=0; static LL inver=0;
    	while(l>x) l--,inver+=qsum(a[l]),upd(a[l],1);
    	while(r<y) r++,inver+=r-l-qsum(a[r]),upd(a[r],1);
    	while(l<x) upd(a[l],-1),inver-=qsum(a[l]),l++;
    	while(r>y) upd(a[r],-1),inver-=r-l-qsum(a[r]),r--;
    	return inver;
    }
    void solve2(int l,int r,int ql,int qr){
    	if(ql>qr) return;
    	int mid=(ql+qr)>>1,p=-1; LL mn=inf,tmp;
    	for(int i=l;i<=r&&i<mid;i++)
    		if((tmp=f[i]+ask(i+1,mid))<mn) mn=tmp,p=i;
    	f[mid]=min(f[mid],mn+X);
    	solve2(l,p,ql,mid-1),solve2(p,r,mid+1,qr);
    }
    void solve1(int l,int r){
    	if(l==r) return;
    	int mid=(l+r)>>1;
    	solve1(l,mid);
    	solve2(l,mid,mid+1,r);
    	solve1(mid+1,r);
    }
    int main()
    {
    	freopen("dispatch.in","r",stdin);
    	freopen("dispatch.out","w",stdout);
    	scanf("%d%d",&n,&X);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=inf;
    	solve1(0,n);
    	printf("%lld\n",f[n]);
    }
    

    要卡常的话可以尝试把 upd 函数写成 ++ 和 --,以及在寻找决策点的循环根据端点位置判断一下顺着循环还是反着循环。

    还有的优化是在 solve1 区间小于分块大小 SS 时暴力做,预处理区间长度 S\le S 的逆序对数,这个可以 O(nS)O(nS) 预处理, wi,j=wi,j1+wi+1,jwi+1,j1+[ai>aj]w_{i,j}=w_{i,j-1}+w_{i+1,j}-w_{i+1,j-1}+[a_i>a_j]

    扩展

    O(nn)O(n\sqrt n) 求区间逆序对个数。

    离线做法:
    莫队,考虑移动端点的时候不使用树状数组,而改为查询区间小于 xx 的数的个数。先跑一遍莫队,得到所有这样 O(nn)O(n\sqrt n) 个询问。
    差分一下就变成了查询一个前缀小于 xx 的数的个数,对值域分块,相当于一个块前缀和一个块内前缀,从前往后扫描,每次加入一个数后 O(n)O(\sqrt n) 修改,查询就是 O(1)O(1) 的。

    在线做法:
    详见 WerKeyTom_FTD的博客
    大致思路是预处理块内贡献,块间贡献,需要算两个小区间之间的贡献时通过块内预先排好序的数组找到区间内排序后的情况,然后归并。

    时空复杂度都是 O(nn)O(n\sqrt n) 的。

    展开全文
  • hdu5273(区间逆序对的个数)

    千次阅读 2015-06-24 09:35:12
    题目的大致意思是有一个数组,然后有Q个询问,对于每次询问给出L和R,然后要给出每次L和R区间内的逆序对个数。  解答方法就是先算出ans[0][1...N-1]的结果,然后根据再来算ans[i][i+1...N-1](0#include "stdio.h" ...

      题目的大致意思是有一个数组,然后有Q个询问,对于每次询问给出L和R,然后要给出每次L和R区间内的逆序对个数。

      解答方法就是先算出ans[0][1...N-1]的结果,然后根据再来算ans[i][i+1...N-1](0<i<N),ans[i][j] 跟ans[i-1][j]相比就是要减去第i个数字的影响,所以开一个累加器即可。

    #include "stdio.h"
    #include "string.h"
    #include "math.h"
    #include <string>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    
    #define MAXM 1
    #define MAXN 1
    #define max(a,b) a > b ? a : b
    #define min(a,b) a < b ? a : b
    #define Mem(a,b) memset(a,b,sizeof(a))
    int Mod = 1000000007;
    double pi = acos(-1.0);
    double eps = 1e-6;
    
    typedef struct{
    	int f,t,w,next;
    }Edge;
    Edge edge[MAXM];
    int head[MAXN];
    int kNum;
    typedef long long LL;
    
    void addEdge(int f, int t, int w)
    {
    	edge[kNum].f = f;
    	edge[kNum].t = t;
    	edge[kNum].w = w;
    	edge[kNum].next = head[f];
    	head[f] = kNum ++;
    }
    
    int dp[1005][1005];
    int cnt[1005];
    int num[1005];
    int N, Q;
    
    void solve(){
    	cin>>Q;
    	Mem(cnt, 0);
    	Mem(dp, 0);
    	for(int i = 0; i < N; i ++){
    		scanf("%d",&num[i]);
    	}
    
    	for(int i = 1; i < N; i ++){
    		dp[0][i] = dp[0][i-1];
    		for(int j = 0; j < i; j ++){
    			if(num[i] < num[j])
    				dp[0][i] ++;
    		}
    	}
    	
    	int jichu; //累加器
    	for(int i = 1; i < N; i ++){
    		if( num[i] < num[i-1] ) jichu = 1;
    		else jichu = 0;
    		for(int j = i + 1;j < N; j ++){
    			if( num[j] < num[i-1] ) jichu ++;
    			dp[i][j] = dp[i-1][j] - jichu;
    		}
    	}
    
    
    	/*for(int i = 1; i < N; i ++){
    		cnt[i] = cnt[i-1];
    		for(int j = 0; j < i; j ++){
    			if( num[i] < num[j] )
    				cnt[i] ++;
    		}
    	}*/
    
    	int L, R;
    	for(int i = 0; i < Q; i ++){
    		scanf("%d %d", &L, &R);
    		printf("%d\n",dp[L-1][R-1]);
    	}
    
    }
    
    
    int main()
    {
    //	freopen("d:\\test.txt", "r", stdin);
    	while(cin>>N){
    		solve();
    	}
    
    	return 0;
    }
    
    

    展开全文
  • 逆序对个数 没有重复数字 线段树实现: 离散化。 单点修改,区间求和// by SiriusRen #include #include #include using namespace std; long long ans=0; int n,t,f[2555555],sum[2555555],a[2555555]; bo

    题意:
    求逆序对个数 没有重复数字
    线段树实现:
    离散化。 单点修改,区间求和

    // by SiriusRen
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    long long ans=0;
    int n,t,f[2555555],sum[2555555],a[2555555];
    bool cmp(int i,int j){return a[i]<a[j];}
    void change(int l,int r,int pos){
        if(l==r){sum[pos]=1;return;}
        int mid=(l+r)>>1;
        if(mid<a[t])change(mid+1,r,pos<<1|1);
        else change(l,mid,pos<<1);
        sum[pos]=sum[pos<<1]+sum[pos<<1|1];
    }
    int query(int l,int r,int pos){
        if(l>a[t]&&r<=n)return sum[pos];
        int mid=(l+r)>>1;
        if(mid<=a[t])return query(mid+1,r,pos<<1|1);
        else return query(mid+1,r,pos<<1|1)+query(l,mid,pos<<1);
    }
    int main(){
        while(scanf("%d",&n)&&n){
            ans=0;
            memset(sum,0,sizeof(sum));
            for(int i=1;i<=n;i++)f[i]=i;
            for(int i=1;i<=n;i++)scanf("%d",&a[i]);
            sort(f+1,f+1+n,cmp);
            for(int i=1;i<=n;i++)a[f[i]]=i;
            for(t=1;t<=n;t++)change(1,n,1),ans+=query(1,n,1);   
            printf("%lld\n",ans);
        }
    }

    归并排序(掌握得不好,,,,以后还是用segtree吧。。。):

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define int long long
    using namespace std;
    int n,a[500005],q[500005],ans=0;
    void solve(int l,int r){
        if(r==l)return;
        int mid=(l+r)/2;
        solve(l,mid);solve(mid+1,r);
        int jy1=l,jy2=mid+1,jy=l;
        while(jy1<=mid||jy2<=r){
            if(jy2>r ||(jy1<=mid&&a[jy1]<=a[jy2]))q[jy++]=a[jy1++];
            else{
                if(jy1<=mid) ans+=jy2-jy;
                q[jy++]=a[jy2++];
            }
        }
        for(int i=l;i<=r;i++)a[i]=q[i];
    }
    signed main(){
        while(scanf("%lld",&n)&&n){
            ans=0;
            for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
            solve(1,n);printf("%lld\n",ans);
        }
    }
    展开全文
  • 题目描述 一只含数字的字符串,q次操作,每次操作将第i位数字改为x,每次操作后,统计长度在[l, r]之间且首数字大于尾数字的子串的个数。输入描述:第一行一只含数字的字符串; 第二行3整数q, l, r; 接下来q...

    题目描述 

    一个只含数字的字符串,q次操作,每次操作将第i位数字改为x,每次操作后,统计长度在[l, r]之间且首数字大于尾数字的子串的个数。

    输入描述:

    第一行一个只含数字的字符串;
    第二行3个整数q, l, r;
    接下来q行,每行两个整数i, x。

    输出描述:

    输出q行,每行一个整数,表示长度在[l, r]之间且首数字大于尾数字的子串的个数。
    示例1

    输入

    585605
    2 2 4
    1 6
    4 2

    输出

    7
    8

    备注:

    设字符串长度为n则:
    1 <= n <= 100000;
    1 <= q <= 100000; 1 <= l <= r <= n; 1 <= i <= n; 0 <= x
    <= 9;

    题解:

    相当于求间隔距离在[l, r]之间的逆序对数。
    因为所有数在[0,9]之间,所以可用 10 个树状数组维护数字每种的前缀和。
    初始化求第一遍 ans 的时候,对于每个数考虑前面与该点的距离在[l,r]之间的所有点。

    每次修改,减去当前位置的数对答案的影响,再加上更新后的数对答案的影响。

    考虑前面和后面与该点的距离在[l,r]之间的所有点,更新 ans 即可。

    时间复杂度:n*logn


    树状数组

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5+10;
    char str[maxn];
    int l,r,len;
    struct BIT
    {
        int c[10][maxn];
        int lowbit(int x) {return x & -x;}
        void init() 
        {
            memset(c,0,sizeof(c));
        }
        void update(int x,int pos,int val)
        {
            for(int i=pos;i<maxn;i+=lowbit(i)) c[x][i] += val;
            return ;  
        }
        int query(int x,int pos) 
        {
            int ans = 0;
            for(int i=pos;i>0;i-=lowbit(i)) ans += c[x][i];
            return ans;
        }
    }bit;
    
    int ask_left(int x,int pos)             /// 统计在[pos-r+1,pos-l+1] 中有多少大于x的 
    {
        int ans = 0;
        for(int i=x+1;i<10;i++) ans += bit.query(i,max(pos-l+1,0)) - bit.query(i,max(pos-r,0));
        return ans;
    }
    int ask_right(int x,int pos,int len)    /// 统计在[pos+l-1,pos+r-1] 中有多少个小于x的
    {
        int ans = 0;
        for(int i=x-1;~i;i--) ans += bit.query(i,min(pos+r-1,len)) - bit.query(i,min(pos+l-2,len));
        return ans;
    }
    int main()
    {
        while(~scanf("%s",str+1))
        {
            bit.init();
            int q;
            scanf("%d%d%d",&q,&l,&r);
            int len = strlen(str+1);
            ll ans = 0;
            for(int i=1;i<=len;i++) {  /// 得出未修改前的总逆序对个数
                int x = str[i]-'0';
                bit.update(x,i,1);
                ans += ask_left(x,i); 
            }
            // printf("%d\n",ans);
            int pos,x;
            while(q--)
            {
                scanf("%d%d",&pos,&x);
                int y = str[pos] - '0';
                ans -= ask_left(y,pos) + ask_right(y,pos,len);  /// 删除当前位置对答案的影响
                bit.update(y,pos,-1);
                str[pos] = x + '0';
                bit.update(x,pos,1);
                ans += ask_left(x,pos) + ask_right(x,pos,len);  /// 增加当前位置对答案的影响
                printf("%lld\n",ans);
            }
        }
        return 0;
    }

    线段树

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5+10;
    ll arr[maxn];
    char str[maxn];
    int l,r,len;
    struct SegTree
    {
        ll sum[maxn<<2];
        void init()
        {
            memset(sum,0,sizeof(sum));
        }
        void push_up(int rt)
        {
            sum[rt] = sum[rt<<1] + sum[rt<<1|1];
        }
        void build(ll arr[],int l,int r,int rt)
        {
            if(l == r) {
                sum[rt] = arr[l];
                return ;
            }
            int mid = (l + r) >> 1;
            build(arr,l,mid,rt<<1);
            build(arr,mid+1,r,rt<<1|1);
            push_up(rt);
        }
        void activate(int pos,ll val,int l,int r,int rt)
        {
            if(l == r) {
                sum[rt] = val;
                return;
            }
            int mid = (l + r) >> 1;
            if(pos <= mid) activate(pos,val,l,mid,rt<<1);
            else activate(pos,val,mid+1,r,rt<<1|1);
            push_up(rt);
        }
        void update(int pos,ll val,int l,int r,int rt)
        {
            if(l == r)
            {
                sum[rt] += val;
                return ;
            }
            int mid = (l + r) >> 1;
            if(pos <= mid) update(pos,val,l,mid,rt<<1);
            else update(pos,val,mid+1,r,rt<<1|1);
            push_up(rt);
        }
        ll query(int ql,int qr,int l,int r,int rt)
        {
            if(ql == l && qr == r) return sum[rt];
            int mid = (l + r) >> 1;
            if(qr <= mid) return query(ql,qr,l,mid,rt<<1);
            if(ql > mid) return query(ql,qr,mid+1,r,rt<<1|1);
            return query(ql,mid,l,mid,rt<<1) + query(mid+1,qr,mid+1,r,rt<<1|1);
        }
    }seg[10];
    ll ask_left(int num,int pos)
    {
        ll res = 0,temp;
        for(int i=num+1;i<10;i++) {
            if(pos-l+1 <= 0) temp = 0;
            else {
                if(pos-r+1 <= 0) temp = seg[i].query(1,pos-l+1,1,len,1);
                else temp = seg[i].query(pos-r+1, pos-l+1,1,len,1);
            } 
            res += temp;
        }
        return res;
    }
    ll ask_right(int num,int pos)
    {
        ll res = 0,temp;
        for(int i=num-1;i>=0;i--) {
            if(pos+l-1>len) temp = 0;
            else {
                if(pos+r-1 > len) temp = seg[i].query(pos+l-1,len,1,len,1);
                else temp = seg[i].query(pos+l-1,pos+r-1,1,len,1);
            }
            res += temp;
        }
        return res;
    }
    int main()
    {
        while(~scanf("%s",str))
        {
            int q;
            scanf("%d%d%d",&q,&l,&r);
            for(int i=0;i<10;i++) seg[i].init();
    
            len = strlen(str);
            for(int i=1;i<=len;i++) arr[i] = str[i-1]^'0';
            
            ll ans = 0;
            for(int i=1;i<=len;i++) {
                seg[arr[i]].update(i,1,1,len,1);
                ans += ask_left(arr[i],i);
            }
            //printf("%lld\n",ans);
    
            int pos,x;
            while(q--)
            {
                scanf("%d%d",&pos,&x);
                int y = arr[pos];
                ans -= ask_left(y,pos) + ask_right(y,pos);
                arr[pos] = x;
                seg[y].update(pos,-1,1,len,1);
                seg[x].update(pos,1,1,len,1);
                ans += ask_left(x,pos) + ask_right(x,pos);
                printf("%lld\n",ans);
            }
        }
        return 0;
    }

    展开全文
  • 接下来,我便从一初学者的角度,来一步步的,讲解一下由树状数组求逆序对。需要的前置知识只有,会线段数组的基本应用。单点更新,区间查询,求lowbit。 先贴树状数组的基本代码。 求lowbit int lowbit(x){return ...
  • nnlognn\sqrt {nlogn}nnlogn​的分块+树状数组处理前i块小于j(及大于j)的有多少,相当于用分块代替了主席树。 nnn\sqrt nnn​的分块,其实可以使上面的方法最后处理散块的时候用散块之间桶排归并,散块自身...
  •  给你一个由1~n构成的正整数序列,有m组询问,每组询问要求输出[l , r]区间内的逆序对个数。 数据范围:  对于100%的数据,满足1 <= n,m <= 30000,l < r,∑ | l[i] - l[i-1] | + ∑ | r[i] - r[i-1] ...
  • 题解: g_ig​i​​表示在ii前面比a_ia​i​​大的数的个数, f_if​i​​表示在ii后面比a_ia​i​​小的数的个数, 这两个都可以用树状数组轻松求出来.... 求区间逆序对个数只要用一个树状数组维护就好了,
  • 在数组中的两数字,如果前面一数字大于后面的数字,则这两数字组成一个逆序对。输入一数组,求出这数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 S1 牛客解法之一: ...
  • HDU.1394 Minimum Inversion Number (线段树 单点更新 区间求和 逆序对)题意分析给出n个数的序列,a1,a2,a3……an,ai∈[0,n-1],求环序列中逆序对最少的个数。前置技能 环序列 还 线段树的逆序对求法 逆序对:ai...
  • 题意:给出1~n的一组排列,求所有区间逆序对个数的和 Input: 第1行输入n(1 第2行输入n个整数a[i](1 Output: 输出一行,所有区间逆序对个数的和,答案太大要求对1e9+7取模 限时:1000ms 限内存:64000kB Sample ...
  • 【问题描述】有 个数,随机选择一段区间,如果这段区间的所有数的平均值在[l , r]中则 你比较厉害。求你比较厉害的概率。【输入格式】第一行有三个数 N,l ,r,含义如上描述。 接下一行有 个数代表每一个数的值。...
  • 牛客 兔子的逆序对 ...需要反转区间 反转区间后不会改变区间外的逆序对个数 ...设区间逆序对个数为x 反转之后 则总逆序对个数为 ans-x+(r-l+1)(r-l)/2-x 整理: ans+(r-l+1)(r-l)/2-2x 2x对整个式子的奇偶性无影响 只
  • 逆序对

    2021-04-21 21:39:41
    a[j],那么俩个数就是逆序对。 我们可以使用归并排序进行求出个数,然后进行二分序列,递归左右两半,合并有序序列。 合并两个序列,可以采用两个指针ij分别进行扫描,不断进行比较指针所在的值,然后加入数组。 ...
  • 兔子的逆序对

    万次阅读 2021-02-23 22:00:29
    兔子觉得只是求一个序列的逆序对个数太没有意思了。 于是兔子想到了一个更有趣的问题! 兔子可以把区间[L,R] 反转,例如序列{1,2,3,4} 反转区间[1,3] 后是{3,2,1,4}。 兔子有m次反转操作,现在兔子想知道每次反转后...
  • 树状数组总结——详解(单点/区间查询, 单点/区间修改, 逆序对) 2017-06-13 17:24 64人阅读 评论(0) 收藏 举报 版权声明:!!!本文为博主原创文章,若转载请附博主链接,一经发现盗版将追究责任。!!! ...
  • 给一个序列(n个数,[0,n-1]每个数无重复),求该序列的逆序数,逆序对-维基百科,然后序列可以做如下操作:序列的第一个值移到序列的结尾,剩下的每个值向前推进一位。 求操作n-1次后,原有的加生成的,总共n种...
  • 逆序对就是序列中 ai>aj且i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目,注意序列中可能有重复数字。 思路: 用一flag数组标记哪些数字已经放入数组中,用线段树求...
  • 逆序数对原理是: 每次输入一新的数字后查询有多少数字比这数字大。如果输入x的话,在统计完成之后,那么更新线段树,更新的是比X大的sum【t(t>x)】++ 查询操作 其中我找了很长时间的bug是 这两if...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 487
精华内容 194
关键字:

区间逆序对个数