「BZOJ1145」[CTSC2008] 图腾totem
Description
在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1, y1) , (2, y2), …, (n, yn)，其中y1~yn是1~N的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（图腾的形式只与4个纵坐标值的相对大小排列顺序有关）：
崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为A类，右边为B类（同样，图腾的形式也都只与4个纵坐标值的大小排列顺序有关）：
小布的团队希望知道，这N个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的值，由于该值可能绝对值较大，本题中只需输出该值对16777216的余数（注意余数必为正值，例如-1对16777216的余数为16777215）。
Input
第一行包含一个整数N，为点的数目。接下来一行包含N个整数，分别为y1, y2, …, yn。保证y1, y2, …, yn是1~N的一个排列。
Output
仅包含一个数，表示闪电图腾数目与山峰图腾数目的差值对16777216的余数。
Sample Input
5
1 5 3 2 4
「样例输入二」
4
1 2 4 3
Sample Output
0
「样例输出二」
16777215
HINT
样例一中共有1个闪电图腾（1324）和1个B类山峰图腾（1532）。样例二中仅有一个A类山峰图腾（1243），故差值为-1，答案为16777215。
「数据规模」对于10%的数据，N ≤ 600；对于40%的数据，N ≤ 5000；对于100%的数据，N ≤ 200000。
题解
这个令我蛋疼了大半天
到现在都没看懂clj神犇说的14XX求法什么意思
所以我参照了下seter的博客
以下如有错误请大家指正。。。
要求的是f[1324]-f[1243]-f[1432]
f[1324]-f[1243]-f[1432]
=(f[1x2x]-f[1423])-(f[12xx]-f[1234])-(f[14xx]-f[1423])
=f[1x2x]+f[1234]+f[13xx]-f[1xxx]
先求出l[i]，r[i]表示在i的左/右，比a[i]小的个数
可以先用树状数组求l[i]，则r[i]=(a[i]-l[i]-1)
———————————————————————————————————
f[1xxx]
枚举(1)的位置i，则i右边比i大的数有n-i-r[i],设为t
则xxx的方案数为t*(t-1)*(t-2)/6
———————————————————————————————————
f[1234]
枚举(3)的位置i，则(4)的个数有n-i-r[i]
12的对数为sigma(l[j]) (a[j]<a[i],j<=i)
两式相乘法
———————————————————————————————————
f[1x2x]
枚举(2)的位置i，则(2)左边的「数字对」(a[x],a[y])(a[x]<a[i],y任意)有l[i]*(i-1)个
但只有a[y]>a[i]，且y>x的合法
多算的有两部分，一部分是a[y]<a[i]，y>x，另一部分y<x
第一部分l[i]*(l[i]-1)/2，第二部分为sigma j (a[j]<a[i])
———————————————————————————————————
f[13xx]
枚举(3)的位置i，(3)的右侧要是(2)(4)或者(4)(2)
(4)的个数n-i-r[i]
则「数字对」(a[x],a[y])(a[x]<a[i],x<i,a[y]<a[i])有l[i]*(a[i]-1)个
但只有a[x]<a[y]，y>i的合法
也多算了两部分，一部分是x<y<i，形如123，另一部分是a[x]<a[y],y<x，形如213
第一部分l[i]*(l[i]-1)/2 第二部分sigma a[j] (a[j]<a[i])
大概这样吧
|
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 91 92 93 94 95 96 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<ctime> #include<vector> #include<set> #include<cmath> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define P 16777215 using namespace std; 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; } int n,res; int a[200005]; ll l[200005],r[200005],t[200005]; void add(int x,int val) { for(int i=x;i<=n;i+=i&-i)t[i]+=val; } ll query(int x) { ll res=0; for(int i=x;i;i-=i&-i)res+=t[i]; return res; } void pre() { for(int i=1;i<=n;i++) { l[i]=query(a[i]); r[i]=a[i]-l[i]-1; add(a[i],1); } } int cal1()//1x2x { memset(t,0,sizeof(t)); ll res=0; for(int i=1;i<=n;i++) { res=(res+(l[i]*(i-1)-query(a[i])-l[i]*(l[i]-1)/2)*(n-r[i]-i))&P; add(a[i],i); } return res; } int cal2()//13xx { memset(t,0,sizeof(t)); ll res=0; for(int i=n;i;i--) { res=(res+(query(a[i])-r[i]*(r[i]+1)/2)*(n-r[i]-i))&P; add(a[i],a[i]); } return res; } int cal3()//1234 { memset(t,0,sizeof(t)); ll res=0; for(int i=1;i<=n;i++) { res=(res+query(a[i])*(n-i-r[i]))&P; add(a[i],l[i]); } return res; } int cal4()//1xxx { ll res=0; for(int i=1;i<=n;i++) { ll t=n-i-r[i]; if(t>=3) res=(res+t*(t-1)*(t-2)/6)&P; } return res; } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); pre(); printf("%d",(cal1()+cal2()+cal3()-cal4())&P); return 0; } |
OI 课件=>
f[13xx]:
多算的2部分应该是ax<ay&&yay?学长貌似没有讨论ax>ay&&y>i的情况?