首页 > 其他分享 >cdq分治/逆序对 一点点总结

cdq分治/逆序对 一点点总结

时间:2024-04-25 16:24:21浏览次数:19  
标签:ch int 分治 aj mid while cdq 逆序

cdq分治/逆序对 一点点总结

归并排序求普通逆序对问题

#include<bits/stdc++.h>
#define IN inline
#define R register int
using namespace std;
const int N=5e5+5;    
typedef long long ll;
IN int read()
{
    int f=1;char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;int x=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') x=x*10+ch-'0';
    return x*f;
}
#define in(x) x=read()
ll ans;
int n,a[N],b[N],k;
void merge_sort(int l,int r)
{
    if(l==r) return ;
    int mid=l+r>>1;
    merge_sort(l,mid);merge_sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) b[k++]=a[i++];
        else 
        {
            ans+=(ll)mid-i+1;
            b[k++]=a[j++];
        }
    } 
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(R i=l;i<k;i++) a[i]=b[i];
}
int main()
{
    in(n);
    for(R i=1;i<=n;i++) a[i]=read();
    merge_sort(1,n);
    printf("%lld",ans);
    return 0;
} 

1.注意不能重复统计

因为一对逆序对(ai,aj)只要在i位置或者j位置统计就好了,所以只要在if else的一个分支里面统计就行

2.统计答案的时机

只要ai > aj,那么mid + 1 ~ j 都比ai小,这时候直接统计就行

 

cdq分治求三维偏序

#include <bits/stdc++.h>
#define R(x) x=read()
using namespace std;

inline int read()
{
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 1e5 + 5, M = 2e5 + 5;

struct Element{
    int a, b, c, cnt, res;
    bool operator != (const Element &tmp) const
    {
        if(a != tmp.a) return true;
        if(b != tmp.b) return true;
        if(c != tmp.c) return true;
        return false;
    }
};

bool cmpA(Element x, Element y)
{
    if(x.a != y.a)  return x.a < y.a;
    if(x.b != y.b)  return x.b < y.b;
    return x.c < y.c;
}

Element e[N], re[N];

int n, k, idx;

//树状数组

int lowbit(int x)
{
    return x & -x;
}

int tr[M];

void update(int x, int v)
{
    for(int i = x; i <= k; i+=lowbit(i))
        tr[i] += v;
    return;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        res += tr[i];
    return res;
}

//临时数组
Element tmpE[N];

bool cmpB(Element x, Element y)
{
    if(x.b != y.b)  return x.b < y.b;
    return x.c < y.c;
}

void solve(int l, int r)
{
    if(l == r)
        return;
    int mid = l + r >> 1;
    solve(l, mid); solve(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    /*while(i <= mid && j <= r)
    {
        if(re[i].b <= re[j].b) 
        {
            update(re[i].c, re[i].cnt);
            re[j].res += query(re[j].c);
            tmpE[k++] = re[i++];
        }
        else
        {
            tmpE[k++] = re[j++];
        }
    }   
    int bI = i;
    while(i <= mid) 
    {
        tmpE[k++] = re[i++];
    }
    while(j <= r)
    {
        re[j].res += query(re[j].c);
        tmpE[k++] = re[j++];
    }
    for(i = l; i <= r; i++)
    {
        if(i < bI)
            update(re[i].c, -re[i].cnt);
        re[i] = tmpE[i];
    }*/
    while(j <= r)
    {
        while(i <= mid && re[i].b <= re[j].b)
        {
            update(re[i].c, re[i].cnt);
            tmpE[k++] = re[i];
            i++;
        }
        re[j].res += query(re[j].c);
        tmpE[k++] = re[j++];
    }
    for(int iI = l; iI < i; iI++)
        update(re[iI].c, -re[iI].cnt);
    while(i <= mid)
        tmpE[k++] = re[i++];
    for(i = l; i <= r; i++)
        re[i] = tmpE[i];
    //sort(re + l, re + r + 1, cmpB);
}

int ans[N];

int main()
{
    R(n);R(k);
    for(int i = 1; i <= n; i++)
    {
        R(e[i].a);R(e[i].b);R(e[i].c);
    }
    //去重
    sort(e + 1, e + n + 1, cmpA);
    int tmpCnt = 0;
    for(int i = 1; i <= n; i++)
    {
        tmpCnt++;
        if(e[i] != e[i + 1])
        {
            re[++idx] = e[i];
            re[idx].cnt = tmpCnt;
            re[idx].res = 0;
            tmpCnt = 0;
        }
    }
    solve(1, idx);
    for(int i = 1; i <= idx; i++)
        ans[re[i].cnt - 1 + re[i].res] += re[i].cnt;
    for(int i = 0; i < n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

统计时机

这个统计时机比普通的逆序对更特殊,不能一出现ai>aj就直接统计,因为这个时候所有能够和aj构成逆序对的数有可能还没有进来,如果每次一遇到ai>aj就统计,就会导致答案重复累加,最终偏大。

所以,我们要把朴素逆序对里的if改成while循环,把所有满足条件的i都遍历过之后,再统计j的贡献。

 

标签:ch,int,分治,aj,mid,while,cdq,逆序
From: https://www.cnblogs.com/smartljy/p/18157936

相关文章

  • CDQ分治
    CDQ分治它是一种非常巧妙地方法。用分治的思想处理三维偏序一类的问题:处理的问题如下:模板有$n$个元素,第$i$个元素有$a_i,b_i,c_i$三个属性,设$f(i)$表示满足$a_j\leqa_i$且$b_j\leqb_i$且$c_j\leqc_i$且$j\nei$的\(j\)的数量。对于......
  • CDQ分治学习笔记
    1.简介CDQ分治是一种思想,类似于动态规划,依照原理和写法的不同,大致分为3类:解决与点对相关的问题1D动态规划的优化及转移通过CDQ分治,将一些动态问题转化为静态问题2.解决与点对相关的问题2.1.流程1.找到序列的中点mid2.将所有的点对(i,j)划分为三类a.\(i\lemi......
  • 点分治小记
    点分治是一类高效统计树上路径问题的算法,通过优化递归深度的方法来有效保证时间复杂度。具体操作一般是以下几步:找到当前子树的重心以重心为根计算经过根节点的路径对答案的贡献将根删去并递归处理它的所有子树因为我们每次都以树的重心来作为根节点,递归深度不会超过......
  • P7431【THUPC2017】小 L 的计算题 (牛顿恒等式)(分治NTT)(多项式求逆)题解
    知识点涉及:牛顿恒等式,分治\(NTT\),多项式求逆。这道题有一个推式子之后分治\(NTT+Ln+Exp\)的做法,不过也有一个不用\(Ln+Exp\)的做法(理论常数要小点,实际差不多)。题解:这道题可以牛顿恒等式直接推出一个非常好写的东西。首先看一下牛顿恒等式的描述:对于\(n\)次多项式\(A(......
  • 点分治
    1概念点分治是树分治的一种,主要用于处理树上路径问题。注意这颗树不需要有根,即这是一颗无根树。下面以例题分析点分治的基本思想。2基本思想首先你需要会的前置知识:树的重心。我们来看这样一道例题:【模板】点分治:给出一颗无根树,有边权,询问树上是否存在距离为\(k\)的......
  • 点分树(动态点分治)学习笔记
    1.定义在点分治的基础上加以变化,构造一颗支持快速修改的重构树,称之为点分树2.算法2.1.思路点分治的核心在于通过树的重心来划分联通块,减少合并层数,从而降低时间复杂度所以,我们可以按分治递归的顺序提出一颗树,易知树高至多为logn具体的说,对于每一个找到的重心,将上一次分治......
  • P1908 逆序对
    原题链接题解本质:求一个数前面有几个数大于它,我们把序列分成几段,然后对每段分别进行排序,然后找出这个数在前面已经排好序中的序列里有几个大于它code#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[500005],b[500005],c[500005];//a-original......
  • 点分治学习笔记
    前置知识:树的重心对于一颗无根树上的每一个点,计算其所有子树中最大的子节点数,这个值最小的点就是树的重心1.定义点分治,又叫树分治,点分治是一种在树上进行路径静态统计的算法,所谓树上的静态统计,并不是像树剖一样维护路径最值,路径之和一类的统计,点分治的本质其实是将一棵树拆分......
  • #莫队二次离线,根号分治#洛谷 5398 [Ynoi2018] GOSICK
    题目\(m\)组询问求\(\sum_{l\leqi,j\leqr}[a_i\bmoda_j==0],n,m,a_i\leq5\times10^5\)分析设\(f(l,r,x)\)表示\(i或j\in[1,x],i或j\in[l,r]\)时的答案,\(g_x\)表示\([1,x]\)的答案,根号的做法可以通过三秒由于涉及区间内的求值,需要在莫队的基础上二次离线,那......
  • [DS 小计] 线段树分治
    很简单的一个小trick。就看能不能想出来。思考我们学过CDQ分治。CDQ分治的思想是把时间切割,询问截断点后面的问题,预处理截断点前面的贡献。这是把问题和修改放在一起的。那么,假设修改很难撤销怎么办?这时候就可以用线段树分治做到只增不删。有点类似回滚莫队。算法直......