基础分治练习题

基础分治练习题

十月 18, 2018

1.1 题目描述

这是一道基础分治练习题。 给你三个数列 {ai}, {bi}, {ci}，保证每个数列都恰好是一个排列。你需要求出满足 ai < aj , bi < bj , ci < cj 的有序对 (i, j) 的数目。

1.2 输入格式

从文件 cdq.in 中读入数据。 数据的第一行包含一个正整数 n，表示数列的长度。接下来一行三个非负整数 SA, SB, SC。 为了避免过量的输入对程序的运行效率产生影响，{ai}, {bi}, {ci} 由以下代码生成：

const int N = 2e6+5;
unsigned int SA,SB,SC;int n,a[N],b[N],c[N];
unsigned int rd()
{
    SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
    unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;
}
void gen(int *P)
{
    for (int i=1;i<=n;++i) P[i]=i;
    for (int i=1;i<=n;++i) swap(P[i],P[1+rd()%n]);
}
int main()
{
    scanf("%d%u%u%u",&n,&SA,&SB,&SC);
    gen(a);gen(b);gen(c);return 0;
}

你可以在程序中自由运行这段代码。在下发文件中提供了这段代码的 cpp 文件，你可以选择直接在 该 cpp 文件下编写程序，也可以假装看不见它。

1.3 输出格式

输出到文件 cdq.out 中。 输出一行一个正整数 ans，表示满足条件的有序对 (i, j) 的对数。

1.4 样例 1 输入

5
233 666 667

1.5 样例 1 输出

4

1.6 样例 1 解释

生成的数列为 a = {1, 2, 3, 4, 5}, b = {1, 5, 3, 2, 4}, c = {3, 4, 2, 1, 5}。 显然有且仅有 (1, 2),(1, 5),(3, 5),(4, 5) 这四个数对满足条件。

1.7 样例 2 输入

100000
123 456 789

1.8 样例 2 输出

1258889897

1.9 子任务

对于 100% 的数据，保证 1 ≤ n ≤ 2 × 106, 1 ≤ SA, SB, SC ≤ 109。 请注意常数因子对程序运行效率带来的影响。 iwGS4U.jpg

1.10 提示

加油！这是道水题！A 掉它

看到这道题的第一眼就是cdq分治。敲开心。然后。。。

iwJNe1.jpg

总之，只要你常数足够优秀（大概八分之一），就可以用cdqA掉此题 然后我们来看看这道神仙题到底在干什么。 根据1.2给出的输入生成程序，我们能一眼看出生成的三个数列其实并木有重复的元素，而且都小于等于n。也就是说，，这三个数列其实都是1~n的排列。 然后我们看看数据范围：2e6，只有O(n)和O(nlogn)两种实际意义的复杂度可以过。那么，我们能想到什么呢？二维偏序是nlogn的。所以，我们可以尝试将题目转成求二维偏序。 我们来看下面这三个东西：

iwJBWD.jpg

明显，对于符合要求的数对，一定会在X,Y,Z中各别计算一次，而对于不符合要求的，只会在X,Y,Z中的一个里被计算一次。那么，我们可以得出：

iwJsQH.jpg

这样，这道题就解决了。（然而我并不知道为什么我一个log还没有两个log快。。。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include <algorithm> //STL¨ª¡§¨®???¡¤¡§
#include <cmath> //?¡§¨°?¨ºy?¡ìo¡¥¨ºy
#include <cstdio> //?¡§¨°?¨º?¨¨?/¨º?3?o¡¥¨ºy
#include <iostream> //¨ºy?Y¨¢¡Â¨º?¨¨?/¨º?3?
#include <cstring> //¡Á?¡¤?¡ä?¡ä|¨¤¨ª
#include <string> //¡Á?¡¤?¡ä?¨¤¨¤
#include <ctime> //?¡§¨°?1?¨®¨²¨º¡À??¦Ì?o¡¥¨ºy
#define itn int
#define fro for
#define ll long long
#define reg register
#define inf 1234567890
#define rep(i,a,b,c) for (register int i=a;i<=b;i+=c)
#define lowbit(x) (x&-x)
/*#include <bitset> //STL???¡¥¨¨Y?¡Â
#include <cstype> //¡Á?¡¤?¡ä|¨¤¨ª
#include <cerrno> //?¡§¨°?¡ä¨ª?¨®??
#include <complex> //?¡ä¨ºy¨¤¨¤
#include <clocale> //?¡§¨°?¡À?¦Ì??¡¥o¡¥¨ºy
#include <cstdlib> //?¡§¨°??¨®??o¡¥¨ºy?¡ã?¨²¡ä?¡¤???o¡¥¨ºy
#include <deque> //STL?????¨®¨¢D¨¨Y?¡Â
#include <exception> //¨°¨¬3¡ê¡ä|¨¤¨ª¨¤¨¤
#include <fstream> //???t¨º?¨¨?/¨º?3?
#include <functional> //STL?¡§¨°?????o¡¥¨ºy(¡ä¨²¨¬?????¡¤?)
#include <limits> //?¡§¨°??¡Â??¨ºy?Y¨¤¨¤D¨ª¡Á??¦Ì3¡ê¨¢?
#include <list> //STL??D?¨¢D¡À¨ª¨¨Y?¡Â
#include <map> //STL¨®3¨¦?¨¨Y?¡Â
#include <iomanip> //2?¨ºy?¡¥¨º?¨¨?/¨º?3?
#include <ios> //?¨´¡À?¨º?¨¨?/¨º?3??¡ì3?
#include <iosfwd> //¨º?¨¨?/¨º?3??¦Ì¨ª3¨º1¨®?¦Ì??¡ã??¨¦¨´?¡Â
#include <istream> //?¨´¡À?¨º?¨¨?¨¢¡Â
#include <ostream> //?¨´¡À?¨º?3?¨¢¡Â
#include <queue> //STL?¨®¨¢D¨¨Y?¡Â
#include <set> //STL?¡¥o?¨¨Y?¡Â
#include <sstream> //?¨´¨®¨²¡Á?¡¤?¡ä?¦Ì?¨¢¡Â
#include <stack> //STL????¨¨Y?¡Â
#include <stdexcept> //¡À¨º¡Á?¨°¨¬3¡ê¨¤¨¤
#include <streambuf> //¦Ì¡Á2?¨º?¨¨?/¨º?3??¡ì3?
#include <utility> //STL¨ª¡§¨®??¡ê¡ã?¨¤¨¤
#include <vector> //STL?¡¥¨¬?¨ºy¡Á¨¦¨¨Y?¡Â
#include <cwchar.h>//?¨ª¡Á?¡¤?¡ä|¨¤¨ª?¡ã¨º?¨¨?/¨º?3?
#include <cwctype.h> //?¨ª¡Á?¡¤?¡¤?¨¤¨¤*/

using namespace std;
int read()
{
trueint x=0,f=1;char ch=getchar();
truewhile (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
truewhile ('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
truereturn x*f;
}

void write(int x)
{
trueint buf[50];
trueif (x<0) putchar('-'),x=-x;
truebuf[0]=0;
truewhile (x) buf[++buf[0]]=x%10,x/=10;
trueif (!buf[0]) buf[0]=1,buf[1]=0;
truewhile (buf[0]) putchar('0'+buf[buf[0]--]);
}

//int find(int x){return fa[x]=fa[x]==x?x:find(fa[x]);}

//void add(int x,int y,int z){to[++cnt]=y;v[cnt]=z;Next[cnt]=head[x];head[x]=cnt;}

const int N=2e6+5;
unsigned int SA,SB,SC;int n,a[N],b[N],c[N];
unsigned int rd(){SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;}
void gen(int *P){rep(i,1,n,1)P[i]=i;rep(i,1,n,1)swap(P[i],P[1+rd()%n]);}
struct P {int a,b,c;}p[2000005];
bool cmpa(const P&A,const P&B){return A.a<B.a;}
bool cmpb(const P&A,const P&B){return A.b<B.b;}
bool cmpc(const P&A,const P&B){return A.c<B.c;}
int t[2000005],q[2000005],l[2000005];
inline void upd(int *a,int x){for(;x<=n;++a[x],x+=lowbit(x));}
inline int get(int *a,int x){int r=0;for(;x;r+=a[x],x-=lowbit(x));return r;}
 
int main(){
    scanf("%d%u%u%u",&n,&SA,&SB,&SC);
    gen(a);gen(b);gen(c);
    register ll X=0, Y=0, Z=0;
    rep(i,1,n,1)  p[i].a=a[i],p[i].b=b[i],p[i].c=c[i];
    sort(p+1, p+n+1, cmpa);rep(i,1,n,1)X+=get(t,p[i].b),upd(t,p[i].b);
    sort(p+1, p+n+1, cmpb);rep(i,1,n,1)Y+=get(q,p[i].c),upd(q,p[i].c);
    sort(p+1, p+n+1, cmpc);rep(i,1,n,1)Z+=get(l,p[i].a),upd(l,p[i].a);
    printf("%lld\n", (X+Y+Z-1ll*n*(n-1)/2)/2);
    return 0;
}

请自动忽视头文件里的乱码以及代码奇怪的高亮

  1. 1. 1.1 题目描述
  2. 2. 1.2 输入格式
  3. 3. 1.3 输出格式
  4. 4. 1.4 样例 1 输入
  5. 5. 1.5 样例 1 输出
  6. 6. 1.6 样例 1 解释
  7. 7. 1.7 样例 2 输入
  8. 8. 1.8 样例 2 输出
  9. 9. 1.9 子任务
  10. 10. 1.10 提示