[关闭]
@cww97 2018-10-24T18:57:35.000000Z 字数 104698 阅读 1597

SaoZhu Team Code Library 2017.11

ACM

for newest edition, click here

这里写图片描述

East China Normal University

Chen WeiWen - Software Engineering cww970329@qq.com

Cao ZhiJie - Computer Science

Zhu XuLiang - Mathematics

常用STL

map的Upperbound

  1. map<int,int>::iterator se = mp.upper_bound(mid);
  2. 返回迭代器

优先队列

  1. priority_queue<int>Q;//采用默认优先级构造队列
  2. priority_queue<int,vector<int>,cmp1>que1;//最小值优先
  3. priority_queue<int,vector<int>,cmp2>que2;//最大值优先
  4. Q.push(x);
  5. int x = Q.top(); Q.pop();

multiset

  1. begin() 返回指向第一个元素的迭代器
  2. clear() 清除所有元素
  3. count() 返回某个值元素的个数
  4. empty() 如果集合为空,返回 true
  5. end() 返回指向最后一个元素的迭代器
  6. erase() 删除集合中的元素 ( 参数是一个元素值,或者迭代器)
  7. find() 返回一个指向被查找到元素的迭代器
  8. insert() 在集合中插入元素
  9. size() 集合中元素的数目
  10. lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器
  11. upper_bound() 返回大于某个值元素的迭代器
  12. equal_range() 返回集合中与给定值相等的上下限的两个迭代器
  13. multiset <point> po;
  14. multiset <point>::iterator L, R, it;

离散化lower_lound

lower_bound 第一个出现的值大于等于val的位置

upper_bound 最后一个大于等于val的位置,也是有一个新元素val进来时的插入位置

  1. sort(a + 1, a + A+1);
  2. A = unique(a + 1, a + A+1) - (a + 1);
  3. for (int i = 1; i <= n; i++){ // segtree
  4. int L = lower_bound(a+1, a+A+1, l[i]) - a;
  5. int R = lower_bound(a+1, a+A+1, r[i]) - a;
  6. T.update(L, R, i, 1, T.M+1,1);
  7. }
  8. ------------use in ChairTree-------------------
  9. for (int i = 1; i <= n; i++) {
  10. scanf("%d", &arr[i]);
  11. Rank[i] = arr[i];
  12. }
  13. sort(Rank + 1, Rank + n+1);//Rank存储原值
  14. int m = unique(Rank + 1, Rank + n +1) - (Rank + 1);//这个m很重要,WA一天系列
  15. for (int i = 1; i <= n; i++) {//离散化后的数组,仅仅用来更新
  16. arr[i] = lower_bound(Rank + 1, Rank + m+1, arr[i]) - Rank;
  17. }
  18. ==================CZJ排序去重===================
  19. sort(vecs.begin(), vecs.end());
  20. vecs.resize(unique(vecs.begin(), vecs.end()) - vecs.begin());

vector 的插入删除

  1. // erase the 6th element
  2. myvector.erase (myvector.begin()+5);
  3. // erase the first 3 elements:
  4. myvector.erase (myvector.begin(),myvector.begin()+3);
  5. // ------------inserting into a vector-----------
  6. #include <iostream>
  7. #include <vector>
  8. int main (){
  9. std::vector<int> myvector (3,100);
  10. std::vector<int>::iterator it;
  11. it = myvector.begin();
  12. it = myvector.insert ( it , 200 );
  13. myvector.insert (it,2,300);
  14. // "it" no longer valid, get a new one:
  15. it = myvector.begin();
  16. std::vector<int> anothervector (2,400);
  17. myvector.insert (it+2,anothervector.begin(),anothervector.end());
  18. int myarray [] = { 501,502,503 };
  19. myvector.insert (myvector.begin(), myarray, myarray+3);
  20. std::cout << "myvector contains:";
  21. for (it=myvector.begin(); it<myvector.end(); it++) std::cout << ' ' << *it;
  22. std::cout << '\n';
  23. return 0;
  24. }

bitset

  1. 构造函数
  2. bitset<n> b;
  3. bn位,每位都为0.参数n可以为一个表达式.
  4. bitset<5> b0;则"b0""00000";
  5. bitset<n> b(unsigned long u);
  6. bn位,并用u赋值;如果u超过n位,则顶端被截除
  7. 如:bitset<5>b0(5);则"b0""00101";
  8. bitset<n> b(string s);
  9. bstring对象s中含有的位串的副本
  10. string bitval ( "10011" );
  11. bitset<5> b0 ( bitval4 );
  12. "b0""10011";
  13. bitset<n> b(s, pos);
  14. bs中从位置pos开始位的副本,前面的多余位自动填充0;
  15. string bitval ("01011010");
  16. bitset<10> b0 ( bitval5, 3 );
  17. "b0" "0000011010";
  18. bitset<n> b(s, pos, num);
  19. bs中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
  20. string bitval ("11110011011");
  21. bitset<6> b0 ( bitval5, 3, 6 );
  22. "b0" "100110";
  23. bool any() 是否存在置为1的二进制位?和none()相反
  24. bool none() 是否不存在置为1的二进制位,即全部为0?和any()相反.
  25. size_t count() 二进制位为1的个数.
  26. size_t size() 二进制位的个数
  27. flip() 把所有二进制位逐位取反
  28. flip(size_t pos)把在pos处的二进制位取反
  29. bool operator[]( size_type _Pos )获取在pos处的二进制位
  30. set() 把所有二进制位都置为1
  31. set(pos) 把在pos处的二进制位置为1
  32. reset() 把所有二进制位都置为0
  33. reset(pos) 把在pos处的二进制位置为0
  34. test(size_t pos)在pos处的二进制位是否为1
  35. unsigned long to_ulong( )用同样的二进制位返回一个unsigned long
  36. string to_string ()返回对应的字符串.

STL补充

Stringstream的使用:

  1.   string str;
  2.   stringstream ss;
  3.   while(getline(cin,str)){ //getline函数的返回值是其中的流cin。一旦cin读取错误就是false。
  4.     ss<<str; //将string送入流中。
  5.     int a,sum=0;
  6.     while(ss >> a) sum+=a; //当流里没有东西的时候,退出循环。
  7.     cout<<sum<<endl;
  8.   }

STL补充
lower_bound: 返回一个ForwardIterator,指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。

upper_bound: 返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置,该位置标志一个大于value的值。重载函数使用自定义比较操作。

inplace_merge: 合并两个有序序列,结果序列覆盖两端范围。重载版本使用输入的操作进行排序。

merge: 合并两个有序序列,存放到另一个序列。重载版本使用自定义的比较。

nth_element: 将范围内的序列重新排序,使所有小于第n个元素的元素都出现在它前面,而大于它的都出现在后面。重载版本使用自定义的比较操作。

sort: 以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。

stable_sort: 与sort类似,不过保留相等元素之间的顺序关系。

unique: 清除序列中重复元素,和remove类似,它也不能真正删除元素。重载版本使用自定义比较操作。

next_permutation: 取出当前范围内的排列,并重新排序为下一个字典序排列。重载版本使用自定义的比较操作。

prev_permutation: 取出指定范围内的序列并将它重新排序为上一个字典序排列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。

scanf 用法及陷阱

格式字符 说明
%c 读入一个字符
%d 读入十进制整数
%i 读入十进制,八进制,十六进制整数
%o 读入八进制整数
%x 读入十六进制整数
%X 同上
%c 读入一个字符
%s 读入一个字符串
%f 读入一个浮点数
%p 读入一个指针
%u 读入一个无符号十进制整数

scanf一个double数据,是%lf,printf一个float或者double都是%f

大写L,加f输出long double。最后的f小写和大写没影响,但是第一个 l 必须大写成L。

unsigned long long %llu

printf 对齐方式

1.默认左对齐

2.在打印数字宽度前面加一个-,左对齐%-10d

3.在数字宽度前面不加-,右对齐%10d

rope

丧心病狂的可持久化平衡树

1)头文件 #include
2)调用命名空间 using namespace __gnu_cxx;

rope适用于大量、冗长的串操作,而不适合单个字符操作

rope本质是封装好的类似块状链表的东东,有人说是logn的,但也有说是n^0.5的。rope不支持一切数值操作,如第k大

先介绍几个可能使用到的函数

1)append()

string &append(const string &s,int pos,int n); // 把字符串s中从pos开始的n个字符连接到当前字符串的结尾

a.append(b);

2)substr()

s.substr(0,5); // 获得字符串s中从第零位开始长度为5的字符串(默认时长度为刚好开始位置到结尾)

定义/声明

rope<char> str;
r="abcdefg"

具体内容
总的来说,

1)运算符:rope支持operator += -= + - < ==
2)输入输出:可以用<<运算符由输入输出流读入或输出。
3)长度/大小:调用length(),size()都可以哦
4)插入/添加等:
push_back(x);  // 在末尾添加x
insert(pos,x);  // 在pos插入x,自然支持整个char数组的一次插入
erase(pos,x);  // 从pos开始删除x个
copy(pos,len,x);  // 从pos开始到pos+len为止用x代替
replace(pos,x);  // 从pos开始换成x
substr(pos,x);  // 提取pos开始x个
at(x)/[x];  // 访问第x个元素

访问

1)迭代器:不说,在竞赛是超时大忌

2)单点访问,直接用数组形式调用下标即可

应用

一、bzoj1269 文本编辑器

实现操作:
1.(已知)move k:移动光标到目标,初始为0
2.(已知)prev:光标前移一个字符
3.(已知)next:光标后移一个字符
4.insert n s:在光标后插入长度为n的字符串s光标位置不变
5.delete n 删除光标后的n个字符,光标位置不变
6.rotate n 反转光标后的n个字符,光标位置不变
7.get 输出光标后一个字符,光标位置不变

solution

为实现反转操作且保证不超时,我们不调用rope自带的可怕函数,暴力构建两个rope,插入时一个正序插入一个倒序插入,区间即为子串赋值

  1. #include<cstdio>
  2. #include<ext/rope>
  3. #include<iostream>
  4. using namespace std;
  5. using namespace __gnu_cxx;
  6. inline int Rin(){
  7. int x=0,c=getchar(),f=1;
  8. for(;c<48||c>57;c=getchar())
  9. if(!(c^45))f=-1;
  10. for(;c>47&&c<58;c=getchar())
  11. x=(x<<1)+(x<<3)+c-48;
  12. return x*f;
  13. }
  14. int n,pos,x,l;
  15. rope<char>a,b,tmp;
  16. char sign[10],ch[1<<22],rch[1<<22];
  17. int main(){
  18. n=Rin();
  19. while(n--){
  20. scanf("%s",sign);
  21. switch(sign[0]){
  22. case'M':pos=Rin();break;
  23. case'P':pos--;break;
  24. case'N':pos++;break;
  25. case'G':putchar(a[pos]);putchar('\n');break;
  26. case'I':
  27. x=Rin();
  28. l=a.length();
  29. for(int i=0;i<x;i++){
  30. do{ch[i]=getchar();}
  31. while(ch[i]=='\n');
  32. rch[x-i-1]=ch[i];
  33. }
  34. ch[x]=rch[x]='\0';
  35. a.insert(pos,ch);
  36. b.insert(l-pos,rch);
  37. break;
  38. case'D':
  39. x=Rin();
  40. l=a.length();
  41. a.erase(pos,x);
  42. b.erase(l-pos-x,x);
  43. break;
  44. case'R':
  45. x=Rin();
  46. l=a.length();
  47. tmp=a.substr(pos,x);
  48. a=a.substr(0,pos)+b.substr(l-pos-x,x)+a.substr(pos+x,l-pos-x);
  49. b=b.substr(0,l-pos-x)+tmp+b.substr(l-pos,pos);
  50. break;
  51. }
  52. }
  53. return 0;
  54. }

线性代数

矩阵快速幂

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  5. typedef long long LL;
  6. const LL MOD = 1000000007LL;
  7. LL n,m;
  8. struct matrix{
  9. static const int MATRIX_N = 11;
  10. LL a[MATRIX_N][MATRIX_N];
  11. int row, col;
  12. matrix():row(MATRIX_N),col(MATRIX_N){memset(a,0,sizeof(a));}
  13. matrix(int x, int y):row(x),col(y){memset(a,0,sizeof(a));}
  14. LL* operator [] (int x){return a[x];}
  15. matrix operator * (matrix x){
  16. matrix tmp(row, x.col);
  17. for(int i = 0; i < row; i++)
  18. for(int j = 0; j < col; j++) if(a[i][j])//稀疏矩阵优化
  19. for(int k = 0; k < x.col; k++) if (x[j][k]){
  20. tmp[i][k] += a[i][j] * x[j][k];
  21. //mult(a[i][j], x[j][k], MOD);
  22. tmp[i][k] %= MOD;
  23. }
  24. return tmp;
  25. }
  26. void operator *= (matrix x){*this = *this * x;}
  27. matrix operator ^ (LL x){
  28. matrix ret(row, col);
  29. for (int i = 0; i < col; i++) ret[i][i] = 1;
  30. matrix tmp = *this;
  31. for (; x; x >>= 1, tmp *= tmp){if (x&1) ret *= tmp;}
  32. return ret;
  33. }
  34. void print(){
  35. for (int i = 0; i < row; i++){
  36. for (int j = 0; j < col; j++) printf("%lld ",a[i][j]);
  37. puts("");
  38. }
  39. }
  40. };
  41. int main() {
  42. LL n;
  43. matrix B(3, 1);
  44. while(scanf("%lld%lld%lld%lld", &B[0][0], &B[1][0], &B[2][0], &n) == 4) {
  45. matrix A(3, 3);
  46. A[0][0] = 0; A[0][1] = 1; A[0][2] = 0;
  47. A[1][0] = 0; A[1][1] = 0; A[1][2] = 1;
  48. A[2][0] = 0; A[2][1] = 1; A[2][2] = 1;
  49. A = A ^ n;
  50. matrix C(3, 1);
  51. C = A * B;
  52. printf("%lld\n", (C[0][0] + C[1][0] + C[2][0]) % MOD);
  53. }
  54. return 0;
  55. }

就是快速幂(czj)

  1. //快速乘法
  2. LL fast_multi(LL m, LL n, LL mod){
  3. LL ans = 0;//注意初始化是0,不是1
  4. n = (n % mod + mod) % mod;
  5. for (;n; n >>= 1){
  6. if (n & 1) ans = (ans + m) % mod;
  7. m = (m + m) % mod;//和快速幂一样,只不过这里是加
  8. }
  9. return ans % mod;
  10. }
  11. LL fast_pow(LL a, LL n, LL mod){//快速幂
  12. LL ans = 1;
  13. for (;n;n >>= 1){
  14. if (n & 1) ans = fast_multi(ans, a, mod) % mod;//不能直接乘
  15. a = fast_multi(a, a, mod) % mod;
  16. }
  17. return ans;
  18. }

线性递推函数杜教模板(快速幂下岗了)

  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <cassert>
  9. using namespace std;
  10. #define rep(i,a,n) for (int i=a;i<n;i++)
  11. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  12. #define pb push_back
  13. #define mp make_pair
  14. #define all(x) (x).begin(),(x).end()
  15. #define fi first
  16. #define se second
  17. #define SZ(x) ((int)(x).size())
  18. typedef vector<int> VI;
  19. typedef long long ll;
  20. typedef pair<int,int> PII;
  21. const ll mod=1000000007;
  22. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  23. // head
  24. int _;
  25. ll n;
  26. namespace linear_seq {
  27. const int N=10010;
  28. ll res[N],base[N],_c[N],_md[N];
  29. vector<ll> Md;
  30. void mul(ll *a,ll *b,ll k) {
  31. rep(i,0,k+k) _c[i]=0;
  32. rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
  33. for (int i=k+k-1;i>=k;i--) if (_c[i])
  34. rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
  35. rep(i,0,k) a[i]=_c[i];
  36. }
  37. int solve(ll n,VI a,VI b) {
  38. ll ans=0,pnt=0;
  39. ll k=SZ(a);
  40. assert(SZ(a)==SZ(b));
  41. rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
  42. Md.clear();
  43. rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
  44. rep(i,0,k) res[i]=base[i]=0;
  45. res[0]=1;
  46. while ((1ll<<pnt)<=n) pnt++;
  47. for (int p=pnt;p>=0;p--) {
  48. mul(res,res,k);
  49. if ((n>>p)&1) {
  50. for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
  51. rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
  52. }
  53. }
  54. rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
  55. if (ans<0) ans+=mod;
  56. return ans;
  57. }
  58. VI BM(VI s) {
  59. VI C(1,1),B(1,1);
  60. int L=0,m=1,b=1;
  61. rep(n,0,SZ(s)) {
  62. ll d=0;
  63. rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
  64. if (d==0) ++m;
  65. else if (2*L<=n) {
  66. VI T=C;
  67. ll c=mod-d*powmod(b,mod-2)%mod;
  68. while (SZ(C)<SZ(B)+m) C.pb(0);
  69. rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
  70. L=n+1-L; B=T; b=d; m=1;
  71. } else {
  72. ll c=mod-d*powmod(b,mod-2)%mod;
  73. while (SZ(C)<SZ(B)+m) C.pb(0);
  74. rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
  75. ++m;
  76. }
  77. }
  78. return C;
  79. }
  80. int gao(VI a,ll n) {
  81. VI c=BM(a);
  82. c.erase(c.begin());
  83. rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
  84. return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
  85. }
  86. };
  87. int main() {
  88. for (scanf("%d",&_);_;_--) {
  89. scanf("%lld",&n);
  90. printf("%d\n",linear_seq::gao(VI{31, 197, 1255, 7997, 50959, 324725, 2069239, 13185773, 84023455},n-2));
  91. }
  92. }

高斯消元(naive)

判断是否有解

求解见红书

  1. int Gauss(matrix a, int m, int n){
  2. int x_cnt = 0;
  3. int col, k; //col为列号,k为行号
  4. for (k=0,col=0;k<m&&col<n; ++k, ++col){
  5. int r = k; //r为第col列的一个1
  6. for (int i=k;i<m;++i) if (a[i][col])r=i;
  7. if (!a[r][col]){ k--; continue;}
  8. if (r!=k)for (int i=col;i<=n;++i)
  9. swap( a[r][i], a[k][i]);
  10. for (int i=k+1;i<m; ++i)if (a[i][col])//消元
  11. for (int j=col;j<=n;++j) a[i][j] ^= a[k][j];
  12. }
  13. for (int i=k;i<m;++i) if (a[i][n])return -1;
  14. if (k<=n)return n-k; //返回自由元个数
  15. }

bitset优化XOR方程组

  1. //HDU 5833 XOR GUASS bitset, 白书P160
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int maxn = 2005;
  5. const int mod = 1e9+7;
  6. int n, vis[maxn], prime[maxn], cnt;
  7. void pre_deal(){
  8. for(int i = 2; i < maxn; i++){
  9. if (vis[i]) continue;
  10. prime[cnt++] = i;
  11. for(int j = i; j < maxn; j += i) vis[j] = 1;
  12. }
  13. }
  14. bitset <330> A[305]; //A[i][j]就表示第j个数的这个i素数是奇数还是偶数
  15. int main(){
  16. pre_deal();
  17. int T, ks = 0; scanf("%d", &T);
  18. while(T--){
  19. printf("Case #%d:\n", ++ks);
  20. for(int i = 0; i < 305; i++) A[i].reset();
  21. scanf("%d", &n);
  22. for(int i = 0; i < n; i++){
  23. long long x;
  24. scanf("%lld", &x);
  25. for(int j = 0; j < cnt; j++){
  26. if(x%prime[j] == 0){
  27. int flag = 0;
  28. while(x%prime[j] == 0){
  29. x /= prime[j];
  30. flag ^= 1;
  31. }
  32. A[j][i] = flag;
  33. }
  34. }
  35. }
  36. int i = 0, j = 0; //xor消元之后j就是秩
  37. for(i = 0; i < n; i++){
  38. int id = -1;
  39. for(int k = j; k < cnt; k++){
  40. if(A[k][i]){id = k; break;}
  41. }
  42. if(id == -1) continue;
  43. swap(A[j], A[id]);
  44. for(int k = j + 1; k < cnt; k++)
  45. if(A[k][i]) A[k] ^= A[j];
  46. j++;
  47. }
  48. int ans = 1;
  49. for(int i = 0; i < n - j; i++) ans = ans * 2 % mod;
  50. ans--;
  51. printf("%d\n", ans);
  52. }
  53. return 0;
  54. }

16行FFT

模板题:多项式乘法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const double PI = acos (-1.);
  4. const int N = 1 << 22;
  5. std::complex <double> AA[N], BB[N];
  6. void fft (std::complex <double> a[], int n, int f) {
  7. for (int i = 0, j = 0; i < n; ++i) {
  8. if (i > j) std::swap (a[i], a[j]);
  9. for (int t = n >> 1; (j ^= t) < t; t >>= 1);
  10. }
  11. static std::complex <double> w[N];
  12. for (int i = 0; i <= n; ++i)
  13. w[i] = std::complex <double> (cos (2 * PI * i / n), sin (2 * PI * i / n));
  14. for (int i = 2; i <= n; i <<= 1)
  15. for (int j = 0; j < n; j += i)
  16. for (int k = 0; k < (i >> 1); ++k) {
  17. std::complex <double> A = a[j + k];
  18. std::complex <double> B = w[f ? n - n / i * k : n / i * k] * a[j + k + (i >> 1)];
  19. a[j + k] = A + B; a[j + k + (i >> 1)] = A - B;
  20. }
  21. if (f) for (int i = 0; i < n; ++i) a[i] = std::complex <double> (a[i].real () / n, a[i].imag ());
  22. }
  23. int main(){
  24. int A, B;
  25. std::cin >> A >> B;
  26. for (int i = 0; i <= A; ++i) {
  27. int u; std::cin >> u;
  28. AA[i] = std::complex <double> (u, 0);
  29. }
  30. for (int i = 0; i <= B; ++i) {
  31. int u; std::cin >> u;
  32. BB[i] = std::complex <double> (u, 0);
  33. }
  34. int n = 1;
  35. while (n <= A + B + 1) n *= 2;
  36. fft (AA, n, 0);
  37. fft (BB, n, 0);
  38. for (int i = 0; i < n; ++i) AA[i] = AA[i] * BB[i];
  39. fft (AA, n, 1);
  40. for (int i = 0; i <= A + B; ++i) std::cout << (int) round (AA[i].real ()) << " \n"[i == A + B];
  41. return 0;
  42. }

NTT(对任意数取模)

  1. // 多项式乘法 系数对MOD=1000000007取模, 常数巨大,慎用
  2. // 只要选的K个素数乘积大于MOD*MOD*N,理论上MOD可以任取。
  3. #define MOD 1000000007
  4. #define K 3
  5. const int m[K] = {1004535809, 998244353, 104857601};
  6. #define G 3
  7. int qpow(int x, int k, int P) {
  8. int ret = 1;
  9. while(k) {
  10. if(k & 1) ret = 1LL * ret * x % P;
  11. k >>= 1;
  12. x = 1LL * x * x % P;
  13. }
  14. return ret;
  15. }
  16. struct _NTT {
  17. int wn[25], P;
  18. void init(int _P) {
  19. P = _P;
  20. for(int i = 1; i <= 21; ++i) {
  21. int t = 1 << i;
  22. wn[i] = qpow(G, (P - 1) / t, P);
  23. }
  24. }
  25. void change(int *y, int len) {
  26. for(int i = 1, j = len / 2; i < len - 1; ++i) {
  27. if(i < j) swap(y[i], y[j]);
  28. int k = len / 2;
  29. while(j >= k) {
  30. j -= k;
  31. k /= 2;
  32. }
  33. j += k;
  34. }
  35. }
  36. void NTT(int *y, int len, int on) {
  37. change(y, len);
  38. int id = 0;
  39. for(int h = 2; h <= len; h <<= 1) {
  40. ++id;
  41. for(int j = 0; j < len; j += h) {
  42. int w = 1;
  43. for(int k = j; k < j + h / 2; ++k) {
  44. int u = y[k];
  45. int t = 1LL * y[k+h/2] * w % P;
  46. y[k] = u + t;
  47. if(y[k] >= P) y[k] -= P;
  48. y[k+h/2] = u - t + P;
  49. if(y[k+h/2] >= P) y[k+h/2] -= P;
  50. w = 1LL * w * wn[id] % P;
  51. }
  52. }
  53. }
  54. if(on == -1) {
  55. for(int i = 1; i < len / 2; ++i) swap(y[i], y[len-i]);
  56. int inv = qpow(len, P - 2, P);
  57. for(int i = 0; i < len; ++i)
  58. y[i] = 1LL * y[i] * inv % P;
  59. }
  60. }
  61. void mul(int A[], int B[], int len) {
  62. NTT(A, len, 1);
  63. NTT(B, len, 1);
  64. for(int i = 0; i < len; ++i) A[i] = 1LL * A[i] * B[i] % P;
  65. NTT(A, len, -1);
  66. }
  67. }ntt[K];
  68. int tmp[N][K], t1[N], t2[N];
  69. int r[K][K];
  70. int CRT(int a[]) {
  71. int x[K];
  72. for(int i = 0; i < K; ++i) {
  73. x[i] = a[i];
  74. for(int j = 0; j < i; ++j) {
  75. int t = (x[i] - x[j]) % m[i];
  76. if(t < 0) t += m[i];
  77. x[i] = 1LL * t * r[j][i] % m[i];
  78. }
  79. }
  80. int mul = 1, ret = x[0] % MOD;
  81. for(int i = 1; i < K; ++i) {
  82. mul = 1LL * mul * m[i-1] % MOD;
  83. ret += 1LL * x[i] * mul % MOD;
  84. if(ret >= MOD) ret -= MOD;
  85. }
  86. return ret;
  87. }
  88. void mul(int A[], int B[], int len) {
  89. for(int id = 0; id < K; ++id) {
  90. for(int i = 0; i < len; ++i) {
  91. t1[i] = A[i];
  92. t2[i] = B[i];
  93. }
  94. ntt[id].mul(t1, t2, len);
  95. for(int i = 0; i < len; ++i) tmp[i][id] = t1[i];
  96. }
  97. for(int i = 0; i < len; ++i){
  98. A[i] = CRT(tmp[i]);
  99. }
  100. }
  101. void init() {
  102. for(int i = 0; i < K; ++i) {
  103. for(int j = 0; j < i; ++j) {
  104. r[j][i] = qpow(m[j], m[i] - 2, m[i]);
  105. }
  106. }
  107. for(int i = 0; i < K; ++i) ntt[i].init(m[i]);
  108. }

单纯形法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int INF=0x3f3f3f3f;
  4. const double EPS=1e-9;
  5. int n,m;
  6. /*
  7. 求解的为标准形式
  8. max z=CX
  9. 满足 AX<=B
  10. X>=0
  11. 约定 B>=0
  12. 对于形式为
  13. min z=CX
  14. 满足 AX >= B
  15. X>=0
  16. 约定B>=0
  17. 可以转换为对偶形式
  18. max w=(B^T)Y
  19. 满足 (A^T)Y<=(C^T)
  20. Y>=0
  21. hint:^T表示矩阵翻转
  22. */
  23. namespace Linear_Programming{
  24. double A[10100][1010],b[10100],c[1010],v;
  25. void Pivot(int l,int e){
  26. int i,j;
  27. b[l] /= A[l][e];
  28. for (i = 1; i <= n; i++) if (i != e)
  29. A[l][i] /= A[l][e];
  30. A[l][e] = 1 / A[l][e];
  31. for(i=1; i<=m; i++)
  32. if(i != l && fabs(A[i][e]) > EPS){
  33. b[i] -= A[i][e] * b[l];
  34. for(j = 1; j <= n; j++) if (j != e)
  35. A[i][j] -= A[i][e] * A[l][j];
  36. A[i][e] = -A[i][e] * A[l][e];
  37. }
  38. v += c[e]*b[l];
  39. for(i=1; i<=n; i++) if(i!=e)
  40. c[i]-=c[e]*A[l][i];
  41. c[e] = -c[e] * A[l][e];
  42. }
  43. double Simplex(){
  44. int i,l,e;
  45. while(1){
  46. for(i=1; i<=n; i++) if(c[i]>EPS) break;
  47. if((e=i) == n+1) return v;
  48. double temp = INF;
  49. for(i = 1; i <= m; i++)
  50. if( A[i][e]>EPS && b[i]/A[i][e]<temp )
  51. temp = b[i] / A[i][e], l = i;
  52. if (temp == INF) return INF;
  53. Pivot(l,e);
  54. }
  55. }

组合数学

常用公式和找规律

  1. 斯特林公式
  2. n! 约等于 sqrt(2*pi*n)*pow(1.0*n/e,n)
  3. 带标号连通图计数
  4. 1 1 1 4 38 728 26704 1866256 251548592
  5. h(n)=2^(n(n-1)/2)
  6. f(n) = h(n)-sum{C(n-1,k-1)*f(k)*h(n-k)}(k=1...n-1)
  7. 不带标号n个节点的有根树计数
  8. 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842,
  9. 不带标号n个节点的树的计数
  10. 1,2,3,6,11,23,47,106,235
  11. OEIS
  12. A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081
  13. 错排公式
  14. D[1] = 0; D[2] = 1;
  15. for(int i = 3; i < 25; i++) {
  16. D[i] = (i - 1) * (D[i - 1] + D[i - 2]);
  17. }
  18. 卡特兰数
  19. 1 2 5 14 42 132 429 1430 4862 16796
  20. binomial(2*n, n)-binomial(2*n, n-1)
  21. Sum_{k=0..n-1} a(k)a(n-1-k)
  22. Stirling数,又称为斯特灵数。
  23.   在组合数学,Stirling数可指两类数,都是由18世纪数学家James Stirling提出的。
  24.   第一类Stirling数是有正负的,其绝对值是包含n个元素的集合分作k个环排列的方法数目。
  25.   第二类Stirling数是把包含n个元素的集合划分为正好k个非空子集的方法的数目。
  26. 递推公式
  27.   第一类Stirling数是有正负的,其绝对值是包含n个元素的集合分作k个环排列的方法数目。
  28.   递推公式为,
  29.   S(n,0) = 0, S(1,1) = 1.
  30.   S(n 1,k) = S(n,k-1) nS(n,k)。
  31.   第二类Stirling数是把包含n个元素的集合划分为正好k个非空子集的方法的数目。
  32.   递推公式为:
  33.   S(n,k)=0; (n<k||k=0)
  34.   S(n,n) = S(n,1) = 1,
  35.   S(n,k) = S(n-1,k-1) kS(n-1,k).
  36. 第一类斯特林数
  37.    有符号Stirling数(无符号Stirling数直接取绝对值)
  38. n=0 1
  39. n=1 0 1
  40. n=2 0 -1 1
  41. n=3 0 2 -3 1
  42. n=4 0 -6 11 -6 1
  43. n=5 0 24 -50 35 -10 1
  44. n=6 0 -120 274 -225 85 -15 1
  45. n=7 0 720 -1764 1624 -735 175 -21 1
  46. 第二类
  47. n=0 1
  48. n=1 0 1
  49. n=2 0 1 1
  50. n=3 0 1 3 1
  51. n=4 0 1 7 6 1
  52. n=5 0 1 15 25 10 1
  53. n=6 0 1 31 90 65 15 1
  54. n=7 0 1 63 301 350 140 21 1
  55. n=8 0 1 127 966 1701 1050 266 28 1
  56. n=9 0 1 255 3025 7770 6951 2646 462 36 1

详解ACM组合数处理,

O(n2)算法——杨辉三角

O(n)算法——阶乘取模 + 乘法逆元

C(m,n) = n! / m! / (n - m)!

如果p是质数,直接quick_mod(b, p-2) % p 费马小定理求逆元

  1. LL C(LL n, LL m){
  2. if(m > n) return 0;
  3. LL ans = 1;
  4. for(int i = 1; i <= m; i++){
  5. LL a = (n + i - m) % MOD;
  6. LL b = i % MOD;
  7. ans = ans * (a * quick_mod(b, p-2) % MOD) % MOD;
  8. }
  9. return ans;
  10. }

如果n,m很大 达到1e18,但是p很小 <= 1e5 ,我们可以利用这个p

Lucas定理:C(n, m) % p = C(n / p, m / p) * C(n%p, m%p) % p

  1. LL Lucas(LL n, LL m){
  2. if(m == 0) return 1;
  3. return C(n % p, m % p) * Lucas(n / p, m / p) % p;
  4. }
  5. void InitFac(){//阶乘预处理
  6. fac[0] = 1;
  7. for(int i=1; i<=n; i++)
  8. fac[i] = (fac[i-1] * i) % MOD;
  9. }
  10. LL C(LL n,LL m,LL p,LL fac[]){
  11. if(n < m) return 0;
  12. return fac[n] * quick_mod(fac[m] * fac[n-m], p - 2, p) % p;
  13. }

组合数奇偶性结论:

如果(n&m) == m 那么c(m,n)是奇数,否则是偶数

生成函数 五边形数定理 整数拆分模板

hdu4658

问一个数n能被拆分成多少种方法,且每一种方法里数字重复个数不能超过k(等于k)。

f[n]=∑(-1)^(k-1)*(f[n-k*(3*k-1)/2]+f[n-k*(3*k+1)/2])

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4. using namespace std;
  5. const int N = 100005;
  6. const int MOD = 1000000007;
  7. int dp[N];
  8. void Init() {
  9. dp[0] = 1;
  10. for(int i=1;i<N;i++){
  11. dp[i] = 0;
  12. for(int j=1;;j++){
  13. int t = (3*j-1)*j / 2;
  14. if(t > i) break;
  15. int tt = dp[i-t];
  16. if(t+j <= i) tt = (tt + dp[i-t-j])%MOD;
  17. if(j&1) dp[i] = (dp[i] + tt)%MOD;
  18. else dp[i] = (dp[i] - tt + MOD)%MOD;
  19. }
  20. }
  21. }
  22. int Work(int n,int k) {
  23. int ans = dp[n];
  24. for(int i=1;;i++){
  25. int t = k*i*(3*i-1) / 2;
  26. if(t > n) break;
  27. int tt = dp[n-t];
  28. if(t + i*k <= n) tt = (tt + dp[n-t-i*k])%MOD;
  29. if(i&1) ans = (ans - tt + MOD)%MOD;
  30. else ans = (ans + tt)%MOD;
  31. }
  32. return ans;
  33. }
  34. int main(){
  35. Init();
  36. int n,k,t;
  37. scanf("%d",&t);
  38. while(t--){
  39. scanf("%d%d",&n,&k);
  40. printf("%d\n",Work(n,k));
  41. }
  42. return 0;
  43. }

容斥原理dfs

题意找与n,m互质的第k个数
思路:二分
找到最小的x,使得小于或等于x的数中满足条件的数的个数大于或等于k
预处理n,m的质因数表
k是深度,也就是当前质因数位置
t是奇偶判断
s是质数乘积
n是传进去的x

  1. void dfs(LL k,LL t,LL s,LL n) {
  2. if(k==num) {
  3. if(t&1) ans-=n/s;
  4. else ans+=n/s;
  5. return;
  6. }
  7. dfs(k+1,t,s,n);
  8. dfs(k+1,t+1,s*fac[k],n); //fac[k]是质因数表
  9. }

//二分调用
dfs(0,0,1,mid);

求(1,b)区间和(1,d)区间里面gcd(x, y) = k的数的对数(1<=x<=b , 1<= y <= d)。
b和d分别除以k之后的区间里面,只需要求gcd(x, y) = 1就可以了,这样子求出的数的对数不变。
这道题目还要求1-3 和 3-1 这种情况算成一种,因此只需要限制就可以了

只需要枚举x,然后确定另一个区间里面有多少个y就可以了。因此问题转化成为区间(1, d)里面与x互素的数的个数
先求出x的所有质因数,因此区间里面是x的质因数倍数的数都不会与x互素,因此,只需要求出这些数的个数,减掉就可以了。
如果w是x的素因子,则(1,d)中是w倍数的数共有d/w个。

容斥原理:
所有不与x互素的数的个数= 1个因子倍数的个数 - 2个因子乘积的倍数的个数 + 3个……-……

答案很大,用long long。
所有数的素因子,预先处理保存一下,不然会超时的。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. #define N 100005
  7. typedef long long ll;
  8. vector<int> x[N];
  9. bool is[N];
  10. void prime() {
  11. memset(is, false, sizeof(is));
  12. for (int i=0; i<N; i++) x[i].clear();
  13. for (int j=2; j<N; j+=2) x[j].push_back(2);
  14. for (int i=3; i<N; i+=2)
  15. if (!is[i]) {
  16. for (int j=i; j<N; j+=i) {
  17. is[j] = true;
  18. x[j].push_back(i);
  19. }
  20. }
  21. }
  22. int work(int u, int s, int w) {
  23. int cnt = 0, v = 1;
  24. for (int i=0; i<x[w].size(); i++) {
  25. if ((1<<i) & s) {
  26. cnt++;
  27. v *= x[w][i];
  28. }
  29. }
  30. int all = u/v;
  31. if (cnt % 2 == 0) return -all;
  32. else return all;
  33. }
  34. int main() {
  35. prime();
  36. int T, a, b, c, d, k;
  37. scanf("%d", &T);
  38. for (int cas=1; cas<=T; cas++) {
  39. scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
  40. if (k == 0) {
  41. printf("Case %d: 0\n", cas);
  42. continue;
  43. }
  44. b /= k, d /= k;
  45. if (b > d) { a = b; b = d; d = a; }
  46. long long ans = 0;
  47. for (int i=1; i<=d; i++) {
  48. k = min(i, b);
  49. ans += k;
  50. for (int j=1; j<(1<<x[i].size()); j++)
  51. ans -= work(k, j, i);
  52. }
  53. printf("Case %d: %I64d\n", cas, ans);
  54. }
  55. return 0;
  56. }

村民排队问题模型

一堆数,其中有一些两两关系,(A,B)表示A在B前面,求排列数

  1. // UVa11174 Stand in a Line
  2. // Rujia Liu
  3. int mul_mod(int a, int b, int n) {
  4. a %= n; b %= n;
  5. return (int)((long long)a * b % n);
  6. }
  7. void gcd(int a, int b, int& d, int& x, int& y) {
  8. if(!b){ d = a; x = 1; y = 0; }
  9. else{ gcd(b, a%b, d, y, x); y -= x*(a/b); }
  10. }
  11. int inv(int a, int n) {
  12. int d, x, y;
  13. gcd(a, n, d, x, y);
  14. return d == 1 ? (x%n+n)%n : -1;
  15. }
  16. #include<cstdio>
  17. #include<cstring>
  18. #include<vector>
  19. using namespace std;
  20. const int maxn = 40000 + 10;
  21. const int MOD = 1000000007;
  22. vector<int> sons[maxn];
  23. int fa[maxn], fac[maxn], ifac[maxn];
  24. int mul_mod(int a, int b) {
  25. return mul_mod(a, b, MOD);
  26. }
  27. // fac[i] = (i!)%MOD, ifac[i]为fac[i]在模MOD下的逆
  28. void preprocess() {
  29. fac[0] = ifac[0] = 1;
  30. for(int i = 1; i < maxn; i++) {
  31. fac[i] = mul_mod(fac[i-1], i);
  32. ifac[i] = inv(fac[i], MOD);
  33. }
  34. }
  35. // 组合数C(n,m)除以MOD的余数
  36. int C(int n, int m) {
  37. return mul_mod(mul_mod(fac[n], ifac[m]), ifac[n-m]);
  38. }
  39. // 统计以u为根的子树有多少种排列。size为该子树的结点总数
  40. int count(int u, int& size) {
  41. int d = sons[u].size();
  42. vector<int> sonsize; // 各子树的大小
  43. size = 1;
  44. int ans = 1;
  45. for(int i = 0; i < d; i++) {
  46. int sz;
  47. ans = mul_mod(ans, count(sons[u][i], sz));
  48. size += sz;
  49. sonsize.push_back(sz);
  50. }
  51. int sz = size-1; // 非根结点的个数
  52. for(int i = 0; i < d; i++) {
  53. ans = mul_mod(ans, C(sz, sonsize[i]));
  54. sz -= sonsize[i];
  55. }
  56. return ans;
  57. }
  58. int main() {
  59. int T;
  60. scanf("%d", &T);
  61. preprocess();
  62. while(T--) {
  63. int n, m;
  64. scanf("%d%d", &n, &m);
  65. memset(fa, 0, sizeof(fa));
  66. for(int i = 0; i <= n; i++) sons[i].clear();
  67. for(int i = 0; i < m; i++) {
  68. int a, b;
  69. scanf("%d%d", &a, &b);
  70. fa[a] = b;
  71. sons[b].push_back(a);
  72. }
  73. // 没有父亲的结点称为虚拟结点的儿子
  74. for(int i = 1; i <= n; i++)
  75. if(!fa[i]) sons[0].push_back(i);
  76. int size;
  77. printf("%d\n", count(0, size));
  78. }
  79. return 0;
  80. }

SG函数,博弈

  1. /**********************
  2. 每组数据都改变策略
  3. **********************/
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cstring>
  7. #include<string>
  8. #include<cmath>
  9. #include<algorithm>
  10. using namespace std;
  11. typedef int LL;
  12. const int MAXN = 1e4 + 5;
  13. const int MAXM = 1e4;
  14. int sg[MAXN];
  15. bool Hash[MAXN];
  16. int f[MAXN];
  17. int N;
  18. void getsg(int n){
  19. memset(sg,0,sizeof sg);
  20. for (int i=1;i<=MAXM;i++){
  21. memset(Hash,false,sizeof Hash);
  22. for(int j = 0; j < N && i >= f[j]; j++) {
  23. Hash[sg[i-f[j]]] = true;
  24. /****************上海大学校赛教训,板不要理解错。
  25. 这不是一堆拆两堆,这是每个可以转移的状态都标记。
  26. ****************/
  27. }
  28. for (int j=0;j<=MAXM;j++){
  29. if (!Hash[j]){
  30. sg[i]=j; break;
  31. }
  32. }
  33. //cout << i << " " << sg[i] << endl;
  34. }
  35. }
  36. int main() {
  37. //freopen("out.txt", "w", stdout);
  38. while(cin >> N, N) {
  39. for(int i = 0; i < N; i++) {
  40. scanf("%d", f + i);
  41. }
  42. sort(f, f + N);//一定要排序
  43. getsg(MAXM);
  44. int m;
  45. cin >> m;
  46. for(int i = 0; i < m; i++) {
  47. int n;
  48. cin >> n;
  49. int ans = 0;
  50. for(int i = 0; i < n; i++) {
  51. int x;
  52. scanf("%d", &x);
  53. ans ^= sg[x];
  54. }
  55. printf("%s", ans ? "W" : "L");
  56. }
  57. printf("\n");
  58. }
  59. return 0;
  60. }
  61. /***************
  62. 独立的棋盘横向移动,看成一个子向另一个子一直在减小,NIM两子间距
  63. ***************/
  64. /***********************
  65. 有一个操作可以把一堆拆成两堆,枚举拆分点
  66. ***********************/
  67. for(int j = 0; j <= i - x; j++) {
  68. Hash[sg[j] ^ sg[i - x - j]] = 1;
  69. }
  70. /***********************
  71. 拿走最后一个的人输,需要特判全是1的情况。
  72. 全是1,分奇偶。不全是1,同直接NIM
  73. ***********************/
  74. /********************
  75. 两维的一样拆分成两个异或。SG[][]两维
  76. 0行,0列特殊处理。直接设置成离原点的距离。
  77. 2 2
  78. .#
  79. ..
  80. 2 2
  81. .#
  82. .#
  83. 0 0
  84. *********************/
  85. /******************
  86. 两个操作,合并两堆,或者取掉1个
  87. ******************/
  88. 最后肯定合并成一堆再一个个取
  89. 如果全大于1,先手可以保证NIM胜利的情况下先合并
  90. 不全为1,后手可以取完一个一堆的,相当于操作了两次。
  91. 此时,DFS+记忆化搜索来解决
  92. dp[i][j]当1的个数为i时,其他全合并起来一共j
  93. 其中的操作包括:
  94. 把某堆只有一个的,取走
  95. 把两堆只有一个的,合并
  96. 把某堆只有一个的,合并给不是一个的
  97. 把不是一个的,取走一个
  98. int dfs(int i, int j) {
  99. if (dp[i][j] != -1) return dp[i][j];
  100. if (j == 1) return dp[i][j] = dfs(i+1, 0);
  101. dp[i][j] = 0;
  102. if (i >= 1 && !dfs(i-1, j)) dp[i][j] = 1;
  103. else if (j >= 1 && !dfs(i, j-1)) dp[i][j] = 1;
  104. else if (i >= 1 && j > 0 && !dfs(i-1, j+1)) dp[i][j] = 1;
  105. else if (i >= 2 && ((j >= 1 && !dfs(i-2, j+3)) || (j == 0 && !dfs(i-2, 2))))
  106. dp[i][j] = 1;
  107. return dp[i][j];
  108. }
  109. /****************
  110. 31 游戏
  111. 1~6各4张
  112. ****************/
  113. 直接搜索,据说记忆化也不用

反nim问题

这题与以往的博弈题的胜负条件不同,谁先走完最后一步谁输,但他也是一类Nim游戏,即为anti-nim游戏。
首先给出结论:先手胜当且仅当
①所有堆石子数都为1且游戏的SG值为0(即有偶数个孤单堆-每堆只有1个石子数);
②存在某堆石子数大于1且游戏的SG值不为0.

数论

fibonacci数列的性质:

1.gcd(fib(n),fib(m))=fib(gcd(n,m))
证明:可以通过反证法先证fibonacci数列的任意相邻两项一定互素,然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m)),递归可求gcd(fib(n),fib(m))=gcd(fib(k),fib(l)),最后k=l,不然继续递归。K是通过展转相减法求出,易证k=gcd(n,m),所以gcd(fib(n),fib(m))=fib(gcd(n,m))。
2.如果fib(k)能被x整除,则fib(k*i)都可以被x整除。
3.f(0)+f(1)+f(2)+…+f(n) = f(n+2)-1
4.f(1)+f(3)+f(5)+…+f(2n-1) = f(2n)
5.f(2)+f(4)+f(6)+…+f(2n) = f(2n+1)-1
6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2 = f(n)·f(n+1)
7.f(0)-f(1)+f(2)-…+(-1)^n·f(n) = (-1)^n·[f(n+1)-f(n)]+1
8.f(n+m) = f(n+1)·f(m)+f(n)*f(m-1)
9.[f(n)]^2 = (-1)^(n-1)+f(n-1)·f(n+1)
10.f(2n-1) = [f(n)]^2-[f(n-2)]^2
11.3f(n) = f(n+2)+f(n-2)
12.f(2n-2m-2)[f(2n)+f(2n+2)] = f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

表为平方和问题以及佩尔方程求解

1 费马平方和定理
奇质数能表示为两个平方数之和的充分必要条件是该素数被4除余1
2 费马平方和定理的拓展定理
正整数能表示为两平方数之和的充要条件是在它的标准分解式中,形如素因子的指数是偶数
3 Brahmagupta–Fibonacci identity
如果两个整数都能表示为两个平方数之和,则它们的积也能表示为两个平方数之和。公式及拓展公式为

这里写图片描述

从这个定理可以看出:如果n不能表示为三个数的平方和,那么n也就不能表示为两个数的平方和。
4 四平方和定理
每个正整数都可以表示成四个整数的平方数之和
5 表为3个数的平方和条件
正整数能表示为三个数的平方和的充要条件是n不能表示成4^m*(8*k+7)的形式。
6 本原勾股数
本原勾股数组(PPT)是一个三元组(a,b,c),其中a,b,c无公因数,且满足a^2 + b^2 =c^2。
s,t为奇数(s > t >= 1),并且gcd(s,t) == 1,那么a = st; b = (s*s-t*t); c = (s*s+t*t)/2;
7 佩尔方程形如x^2-D*y^2=1(D是一个固定的正整数且D不是完全平方数)的方程称为佩尔方程
佩尔方程总有正整数解,若(x1,y1)是使x1最小的解,则每个解(xk,yk)都可以通过取幂得到: 
xk + yk*sqrt(D) = (x1 + y1*sqrt(D))^k 
也有:xn+1 = x0*xn + D*y0*yn, yn+1 = y0*xn + x0*yn; 
xn+2 = 2x0*xn+1-xn,yn+2 = 2x0*yn+1-yn

反素数

给一个数n,求一个最小的正整数,使得它的因子个数为n。

  1. int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
  2. LL n, ans;
  3. void dfs(int dept, ULL tmp, int num){
  4. if(num > n) return;
  5. if(num == n && ans > tmp) ans = tmp;
  6. for(int i=1;i<=63;i++){
  7. if(ans / p[dept] < tmp) break;
  8. dfs(dept+1,tmp *= p[dept], num*(i+1));
  9. }
  10. }
  11. int main(){
  12. while(cin>>n){
  13. ans = INF;
  14. dfs(0,1,1);
  15. cout << ans << endl;
  16. }
  17. return 0;
  18. }

欧拉筛

  1. #include <cstring>
  2. using namespace std;
  3. int prime[1100000],primesize,phi[11000000];
  4. bool isprime[11000000];
  5. void getlist(int listsize){
  6. memset(isprime, 1, sizeof(isprime));
  7. isprime[1] = false;
  8. for(int i=2;i<=listsize;i++){
  9. if(isprime[i]) prime[++primesize]=i;
  10. for(int j = 1; j <= primesize && i*prime[j] <= listsize;j++){
  11. isprime[i*prime[j]] = false;
  12. if(i%prime[j] == 0) break;
  13. }
  14. }
  15. }

莫比乌斯函数模板

  1. void Init(){
  2. memset(vis,0,sizeof(vis));
  3. mu[1] = 1;
  4. cnt = 0;
  5. for(int i=2; i<N; i++){
  6. if(!vis[i]){
  7. prime[cnt++] = i;
  8. mu[i] = -1;
  9. }
  10. for(int j=0; j<cnt&&i*prime[j]<N; j++){
  11. vis[i*prime[j]] = 1;
  12. if(i%prime[j]) mu[i*prime[j]] = -mu[i];
  13. else{
  14. mu[i*prime[j]] = 0;
  15. break;
  16. }
  17. }
  18. }
  19. }

乘法逆元

  1. //扩展欧几里得(扩展gcd)
  2. LL ex_gcd(LL a,LL b,LL &x,LL &y){
  3. if (a == 0 && b == 0) return -1;
  4. if (b == 0){x = 1; y = 0; return a;}
  5. LL d=ex_gcd(b, a % b, y, x);
  6. y -= a / b * x;
  7. return d;
  8. }
  9. //乘法逆元
  10. LL mod_inverse(LL a,LL n){
  11. LL x,y;
  12. LL d = ex_gcd(a,n,x,y);
  13. return (x % n + n) % n;
  14. }
  15. //p是质数可以 快速幂p-2
  16. LL quick_mod(LL a, LL b){
  17. LL ans = 1;
  18. a %= MOD;
  19. for(;b; b >>= 1, a = a*a % MOD){
  20. if(b & 1) ans = ans * a % MOD;
  21. }
  22. return ans;
  23. }
  24. //逆元筛:求1-MAXN的所有关于MOD的逆元
  25. inv[0] = 0; inv[1] = 1;
  26. for(i = 2; i < MAXN; i++){
  27. inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
  28. f[i] = (f[i-1] * i) % MOD;
  29. }

二次同余方程的解

  1. LL quick_mod(LL a, LL b, LL m){} //快速幂
  2. struct T { LL p, d; };
  3. LL w;
  4. //二次域乘法
  5. T multi_er(T a, T b, LL m) {
  6. T ans;
  7. ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m;
  8. ans.d = (a.p * b.d % m + a.d * b.p % m) % m;
  9. return ans;
  10. }
  11. //二次域上快速幂
  12. T power(T a, LL b, LL m) {
  13. T ans;
  14. ans.p = 1;
  15. ans.d = 0;
  16. while(b) {
  17. if(b & 1) {
  18. ans = multi_er(ans, a, m);
  19. b--;
  20. }
  21. b >>= 1;
  22. a = multi_er(a, a, m);
  23. }
  24. return ans;
  25. }
  26. //求勒让德符号
  27. LL Legendre(LL a, LL p) {
  28. return quick_mod(a, (p-1)>>1, p);
  29. }
  30. LL mod(LL a, LL m) {
  31. a %= m;
  32. if(a < 0) a += m;
  33. return a;
  34. }
  35. LL Solve(LL n,LL p) {
  36. if(p == 2) return 1;
  37. if (Legendre(n, p) + 1 == p) return -1;
  38. LL a = -1, t;
  39. while(true){
  40. a = rand() % p;
  41. t = a * a - n;
  42. w = mod(t, p);
  43. if(Legendre(w, p) + 1 == p) break;
  44. }
  45. T tmp;
  46. tmp.p = a;
  47. tmp.d = 1;
  48. T ans = power(tmp, (p + 1)>>1, p);
  49. return ans.p;
  50. }
  51. int main(){
  52. int t; scanf("%d", &t);
  53. while(t--){
  54. int n, p;
  55. scanf("%d %d",&n,&p);
  56. n %= p;
  57. int a = Solve(n, p);
  58. if(a == -1){
  59. puts("No root");
  60. continue;
  61. }
  62. int b = p - a;
  63. if(a > b) swap(a, b);
  64. if(a == b)
  65. printf("%d\n",a);
  66. else
  67. printf("%d %d\n",a,b);
  68. }
  69. return 0;
  70. }

预处理所有数的因数

  1. //预处理所有数的因数表
  2. //SPEED: ECNUOJ 1E6 5000MS O(nlogn)
  3. const int N = 100000 + 5;
  4. vector<int > factor[N];
  5. void init(){
  6. for(int i = 2; i < N; i ++){
  7. for(int j = i; j < N; j += i){
  8. factor[j].push_back(i);
  9. }
  10. }
  11. }
  12. //预处理质因数表
  13. vector<int> x[N];
  14. bool is[N];
  15. void prime() {
  16. memset(is, false, sizeof(is));
  17. for (int i=0; i<N; i++) x[i].clear();
  18. for (int j=2; j<N; j+=2) x[j].push_back(2);
  19. for (int i=3; i<N; i+=2)
  20. if (!is[i]) {
  21. for (int j=i; j<N; j+=i) {
  22. is[j] = true;
  23. x[j].push_back(i);
  24. }
  25. }
  26. }

随机素数测试和大数分解(POJ 1811)

  1. /***************************************************
  2. * Miller_Rabin 算法进行素数测试
  3. * 速度快,可以判断一个 < 2^63 的数是不是素数
  4. ****************************************************/
  5. const int S = 8; //随机算法判定次数,一般8~10就够了
  6. // 快速乘法,计算ret = (a*b)%c a,b,c < 2^63
  7. long long mult_mod(long long a,long long b,long long c)
  8. // 快速幂,计算 ret = (a^n)%mod
  9. long long pow_mod(long long a,long long n,long long mod)
  10. // 通过 a^(n-1)=1(mod n)来判断n是不是素数
  11. // n-1 = x*2^t 中间使用二次判断
  12. // 是合数返回true, 不一定是合数返回false
  13. bool check(long long a,long long n,long long x,long long t){
  14. long long ret = pow_mod(a,x,n);
  15. long long last = ret;
  16. for(int i = 1; i <= t; i++){
  17. ret = mult_mod(ret,ret,n);
  18. if(ret == 1 && last != 1 && last != n-1)return true;//合数
  19. last = ret;
  20. }
  21. if(ret != 1)return true;
  22. else return false;
  23. }
  24. //**************************************************
  25. // Miller_Rabin算法
  26. // 是素数返回true,(可能是伪素数)
  27. // 不是素数返回false
  28. //**************************************************
  29. bool Miller_Rabin(long long n){
  30. if (n < 2) return false;
  31. if (n == 2) return true;
  32. if ((n&1) == 0) return false;//偶数
  33. long long x = n - 1, t = 0;
  34. for(; (x&1)==0;){x >>= 1; t++;}
  35. srand(time(NULL));/* *************** */
  36. for(int i = 0; i < S; i++){
  37. long long a = rand()%(n-1) + 1;
  38. if( check(a,n,x,t) ) return false;
  39. }
  40. return true;
  41. }
  42. //**********************************************
  43. // pollard_rho 算法进行质因素分解
  44. //*********************************************
  45. long long factor[100];//质因素分解结果(刚返回时时无序的)
  46. int tol;//质因素的个数,编号0~tol-1
  47. long long gcd(long long a,long long b)
  48. //找出一个因子
  49. long long pollard_rho(long long x,long long c){
  50. long long i = 1, k = 2;
  51. srand(time(NULL));
  52. long long x0 = rand()%(x-1) + 1;
  53. long long y = x0;
  54. while(1){
  55. i ++;
  56. x0 = (mult_mod(x0,x0,x) + c)%x;
  57. long long d = gcd(y - x0,x);
  58. if( d != 1 && d != x)return d;
  59. if(y == x0) return x;
  60. if(i == k){y = x0; k += k;}
  61. }
  62. }
  63. //对 n进行素因子分解,存入factor. k设置为107左右即可
  64. void findfac(long long n,int k){
  65. if(n == 1)return;
  66. if(Miller_Rabin(n)){
  67. factor[tol++] = n;
  68. return;
  69. }
  70. long long p = n;
  71. int c = k;
  72. while( p >= n) p = pollard_rho(p,c--);//值变化,防止死循环k
  73. findfac(p,k);
  74. findfac(n/p,k);
  75. }
  76. //POJ 1811
  77. //给出一个N(2 <= N < 2^54),如果是素数,输出"Prime",否则输出最小的素因子
  78. int main(){
  79. int T; scanf("%d",&T); long long n;
  80. while(T--){
  81. scanf("%I64d",&n);
  82. if(Miller_Rabin(n)) printf("Prime\n");
  83. else{
  84. tol = 0;
  85. findfac(n,107);
  86. long long ans = factor[0];
  87. for(int i = 1; i < tol; i++)
  88. ans = min(ans,factor[i]);
  89. printf("%I64d\n",ans);
  90. }
  91. }
  92. return 0;
  93. }

中国剩余定理

  1. //可以不满足两两互质
  2. int n;
  3. //扩展gcd多了一个变量
  4. void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y){
  5. if (!b) {d = a, x = 1, y = 0;}
  6. else{
  7. ex_gcd(b, a % b, d, y, x);
  8. y -= x * (a / b);
  9. }
  10. }
  11. LL ex_crt(LL *m, LL *r, int n){
  12. LL M = m[1], R = r[1], x, y, d;
  13. for (int i = 2; i <= n; ++i){
  14. ex_gcd(M, m[i], d, x, y);
  15. if ((r[i] - R) % d) return -1;
  16. x = (r[i] - R) / d * x % (m[i] / d); //m[i]为LL范围时,此处会爆LL
  17. R += x * M;
  18. M = M / d * m[i];
  19. R %= M;
  20. }
  21. return R > 0 ? R : R + M;
  22. }

离散对数(关于方程x^A=B(mod C)的解)

首先判断是否有解,即 a,p 是否互质。不互质即无解。不妨令 x = im − j, 其中
m = ⌈ √ q⌉ , 这样问题变为求得一组 i j 使得条件满足。此时原式变为 a im−j ≡ b (Mod p), 移
项化简得 (a m ) i ≡ ba j (Mod p)。这个时候我们只需穷举 i,j 使得式子成立即可。先从让 j 从
[0,m] 中穷举,并用 hash 记录下 ba j 对应的 j 值。相同的 ba j 记录较大的 j. 接着让 i 从 [1,m]
中穷举,如果 (a m ) i 在 hash 表中有对应的 j 存在,则对应的 im − j 是一组解。其中第一次出
现的为最小的解。

  1. map<LL, int> Hash;
  2. LL i, j;
  3. LL bsgs(LL a, LL b, LL p){
  4. LL xx, yy;
  5. if (exgcd(a, p, xx, yy) != 1)return 1;
  6. a %= p;
  7. LL m = ceil(sqrt(p));
  8. Hash.clear();
  9. LL tmp, ans = b % p;
  10. for (int i = 0; i <= m; ++i){
  11. Hash[ans] = i;
  12. ans = ans * a % p;
  13. }
  14. tmp = f(a, m, p);
  15. ans = 1;
  16. for (int i = 1; i <= m; ++i){
  17. ans = ans * tmp % p;
  18. if (Hash[ans] != 0) return i * m Hash[ans];
  19. }
  20. return 1;
  21. }

字符串

字符串EL哈希

from AcDreamer

  1. unsigned int ELFhash(char *str){
  2. unsigned int h = 0;
  3. unsigned int x;
  4. while(*str){
  5. h = (h << 4) + *str++;
  6. x = h & 0xF0000000L;
  7. if(x){
  8. h ^= x>>24;
  9. h &= ~x;
  10. }
  11. }
  12. return h & 0x7FFFFFFF;
  13. }

双哈希

  1. const ll p1=4373,p2=4789;
  2. const ll mod1=998244353,mod2=1e9+7;
  3. const int N=4096;
  4. ll xp1[27],xp2[27];
  5. ll h1[2][N],h2[2][N];
  6. int len1,len2;
  7. char s[N];
  8. map<int ,int >H1,H2;
  9. bool check(int x){
  10. H1.clear();
  11. H2.clear();
  12. for (int i=1;i<=len1;i++){
  13. if (i+x-1>len1) break;
  14. int t1=(h1[0][i+x-1]-h1[0][i-1]+mod1)%mod1;
  15. int t2=(h1[1][i+x-1]-h1[1][i-1]+mod2)%mod2;
  16. H1[t1]=1;
  17. H2[t2]=1;
  18. }
  19. for (int i=1;i<=len2;i++){
  20. if (i+x-1>len2) break;
  21. int t1=(h2[0][i+x-1]-h2[0][i-1]+mod1)%mod1;
  22. int t2=(h2[1][i+x-1]-h2[1][i-1]+mod2)%mod2;
  23. if (H1[t1]!=0&&H2[t2]!=0) return 1;
  24. }
  25. return 0;
  26. }
  27. int main(){
  28. xp1[0]=xp2[0]=1;
  29. for (int i=1;i<=26;i++){
  30. xp1[i]=(1ll*xp1[i-1]*p1)%mod1;
  31. xp2[i]=(1ll*xp2[i-1]*p2)%mod2;
  32. }
  33. scanf("%s",s+1);
  34. len1=strlen(s+1);
  35. for (int i=1;i<=len1;i++){
  36. h1[0][i]=(h1[0][i-1]+xp1[s[i]-'a'])%mod1;
  37. h1[1][i]=(h1[1][i-1]+xp2[s[i]-'a'])%mod2;
  38. }
  39. scanf("%s",s+1);
  40. len2=strlen(s+1);
  41. for (int i=1;i<=len2;i++){
  42. h2[0][i]=(h2[0][i-1]+xp1[s[i]-'a'])%mod1;
  43. h2[1][i]=(h2[1][i-1]+xp2[s[i]-'a'])%mod2;
  44. }
  45. int ans;
  46. for (ans=min(len1,len2);ans>=0;ans--){
  47. if (ans==0)
  48. printf("%d\n",ans);
  49. else{
  50. if (check(ans)){
  51. printf("%d\n",ans);
  52. return 0;
  53. }
  54. }
  55. }
  56. return 0;
  57. }

Manacher算法(回文串)

  1. #include<cstdio>
  2. #include<string>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. using namespace std;
  7. const int N=233333;//20W
  8. //在o(n)时间内算出以每个点为中心的最大回文串长度
  9. int Manacher(string st){
  10. int len = st.size();
  11. int *p = new int[len+1];
  12. memset(p,0,sizeof(p));
  13. int mx = 0,id = 0;
  14. for (int i = 1;i <= len; i++){
  15. if (mx > i) p[i] = min(p[2*id-i],mx-i);
  16. else p[i] = 1;
  17. while (st[i+p[i]] == st[i-p[i]]) p[i]++;
  18. if (i + p[i] > mx){mx = i + p[i]; id = i;}
  19. }
  20. int ma = 0;
  21. for (int i = 1; i < len; i++) ma = max(ma, p[i]);
  22. delete(p);
  23. return ma - 1;
  24. }
  25. int main(){
  26. //freopen("fuck.in","r",stdin);
  27. char st[N];
  28. while (~scanf("%s",st)){
  29. string st0="$#";
  30. for (int i=0; st[i] != '\0'; i++){
  31. st0 += st[i]; st0 += "#";
  32. }
  33. printf("%d\n", Manacher(st0));
  34. }
  35. return 0;
  36. }

KMP(字符串匹配)

  1. #include<cstdio>
  2. #include<cstring>
  3. using namespace std;
  4. typedef long long LL;
  5. const int N=100007;
  6. const int P=1000000007;
  7. char a[N],b[N];
  8. bool mat[N];
  9. int Next[N];//一定要Next,next会CE
  10. LL f[N];
  11. void getNext(int m, char b[]){
  12. int i = 0,j = -1;
  13. Next[0] = -1;
  14. while (i < m){
  15. if (j == -1 || b[i] == b[j]){
  16. if (b[++i] != b[++j]) Next[i]=j;
  17. else Next[i] = Next[j];
  18. }else j = Next[j];
  19. }
  20. }
  21. //主程序里每组数据需要memset a,b数组!!!
  22. void KMP(int n,char a[], int m, char b[]){
  23. memset(mat, 0, sizeof(mat));
  24. int i = 0, j = 0;
  25. getNext(m, b);//这行视情况可以放在main里面
  26. while (i < n && j < m){
  27. if (j == -1 || a[i] == b[j]) i++, j++;
  28. else j = Next[j];
  29. if (!i && !j)break;
  30. if (j == m){
  31. mat[i] = 1;
  32. //printf("mat[%d]get\n",i);
  33. j = Next[j];
  34. }
  35. }
  36. }

01Tire树

  1. //01字典树的实现可以看成是把一个数的二进制字符化后插入到一颗一般的字典树中
  2. //查找最大异或值的时候我们是从最高位 向下贪心查找 贪心策略为:当前查找第k位 二进制数位IDX 如果存在IDX ^ 1的节点 我们就进入这个节点 否则进入IDX节点
  3. const int maxn = 100000 + 5; //集合中的数字个数
  4. typedef long long LL;
  5. int ch[32 * maxn][2]; //节点的边信息
  6. LL value[32 * maxn]; //节点存储的值
  7. int node_cnt; //树中当前节点个数
  8. inline void init(){ //树清空
  9. node_cnt = 1;
  10. memset(ch[0],0,sizeof(ch));
  11. }
  12. inline void Insert(LL x){ //在字典树中插入 X
  13. //和一般字典树的操作相同 将X的二进制插入到字典树中
  14. int cur = 0;
  15. for(int i = 32;i >= 0;--i){
  16. int idx = (x >> i) & 1;
  17. if(!ch[cur][idx]){
  18. memset(ch[node_cnt],0,sizeof(ch[node_cnt]));
  19. ch[cur][idx] = node_cnt;
  20. value[node_cnt++] = 0;
  21. }
  22. cur = ch[cur][idx];
  23. }
  24. value[cur] = x; //最后的节点插入value
  25. }
  26. inline LL Query(LL x){ //在字典树中查找和X异或的最大值的元素Y 返回Y的值
  27. int cur = 0;
  28. for(int i = 32;i >= 0;--i){
  29. int idx = (x >> i) & 1;
  30. if(ch[cur][idx ^ 1]) cur = ch[cur][idx ^ 1];
  31. else cur = ch[cur][idx];
  32. }
  33. return value[cur];
  34. }

Tire树_刘汝佳

  1. // LA3942 Remember the Word
  2. // Rujia Liu
  3. #include<cstring>
  4. #include<vector>
  5. using namespace std;
  6. const int maxnode = 4000 * 100 + 10;
  7. const int sigma_size = 26;
  8. // 字母表为全体小写字母的Trie
  9. struct Trie {
  10. int ch[maxnode][sigma_size];
  11. int val[maxnode];
  12. int sz; // 结点总数
  13. void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } // 初始时只有一个根结点
  14. int idx(char c) { return c - 'a'; } // 字符c的编号
  15. // 插入字符串s,附加信息为v。注意v必须非0,因为0代表“本结点不是单词结点”
  16. void insert(const char *s, int v) {
  17. int u = 0, n = strlen(s);
  18. for(int i = 0; i < n; i++) {
  19. int c = idx(s[i]);
  20. if(!ch[u][c]) { // 结点不存在
  21. memset(ch[sz], 0, sizeof(ch[sz]));
  22. val[sz] = 0; // 中间结点的附加信息为0
  23. ch[u][c] = sz++; // 新建结点
  24. }
  25. u = ch[u][c]; // 往下走
  26. }
  27. val[u] = v; // 字符串的最后一个字符的附加信息为v
  28. }
  29. // 找字符串s的长度不超过len的前缀
  30. void find_prefixes(const char *s, int len, vector<int>& ans) {
  31. int u = 0;
  32. for(int i = 0; i < len; i++) {
  33. if(s[i] == '\0') break;
  34. int c = idx(s[i]);
  35. if(!ch[u][c]) break;
  36. u = ch[u][c];
  37. if(val[u] != 0) ans.push_back(val[u]); // 找到一个前缀
  38. }
  39. }
  40. };
  41. #include<cstdio>
  42. const int maxl = 300000 + 10; // 文本串最大长度
  43. const int maxw = 4000 + 10; // 单词最大个数
  44. const int maxwl = 100 + 10; // 每个单词最大长度
  45. const int MOD = 20071027;
  46. int d[maxl], len[maxw], S;
  47. char text[maxl], word[maxwl];
  48. Trie trie;
  49. int main() {
  50. int kase = 1;
  51. while(scanf("%s%d", text, &S) == 2) {
  52. trie.clear();
  53. for(int i = 1; i <= S; i++) {
  54. scanf("%s", word);
  55. len[i] = strlen(word);
  56. trie.insert(word, i);
  57. }
  58. memset(d, 0, sizeof(d));
  59. int L = strlen(text);
  60. d[L] = 1;
  61. for(int i = L-1; i >= 0; i--) {
  62. vector<int> p;
  63. trie.find_prefixes(text+i, L-i, p);
  64. for(int j = 0; j < p.size(); j++)
  65. d[i] = (d[i] + d[i+len[p[j]]]) % MOD;
  66. }
  67. printf("Case %d: %d\n", kase++, d[0]);
  68. }
  69. return 0;
  70. }

压缩Tire树

  1. // UVa11732 strcmp() Anyone?
  2. // Rujia Liu
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<vector>
  6. using namespace std;
  7. const int maxnode = 4000 * 1000 + 10;
  8. const int sigma_size = 26;
  9. // 字母表为全体小写字母的Trie
  10. struct Trie {
  11. int head[maxnode]; // head[i]为第i个结点的左儿子编号
  12. int next[maxnode]; // next[i]为第i个结点的右兄弟编号
  13. char ch[maxnode]; // ch[i]为第i个结点上的字符
  14. int tot[maxnode]; // tot[i]为第i个结点为根的子树包含的叶结点总数
  15. int sz; // 结点总数
  16. long long ans; // 答案
  17. void clear() { sz = 1; tot[0] = head[0] = next[0] = 0; } // 初始时只有一个根结点
  18. // 插入字符串s(包括最后的'\0'),沿途更新tot
  19. void insert(const char *s) {
  20. int u = 0, v, n = strlen(s);
  21. tot[0]++;
  22. for(int i = 0; i <= n; i++) {
  23. // 找字符a[i]
  24. bool found = false;
  25. for(v = head[u]; v != 0; v = next[v])
  26. if(ch[v] == s[i]) { // 找到了
  27. found = true;
  28. break;
  29. }
  30. if(!found) {
  31. v = sz++; // 新建结点
  32. tot[v] = 0;
  33. ch[v] = s[i];
  34. next[v] = head[u];
  35. head[u] = v; // 插入到链表的首部
  36. head[v] = 0;
  37. }
  38. u = v;
  39. tot[u]++;
  40. }
  41. }
  42. // 统计LCP=u的所有单词两两的比较次数之和
  43. void dfs(int depth, int u) {
  44. if(head[u] == 0) // 叶结点
  45. ans += tot[u] * (tot[u] - 1) * depth;
  46. else {
  47. int sum = 0;
  48. for(int v = head[u]; v != 0; v = next[v])
  49. sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串,其他子树中再选一个
  50. ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次
  51. for(int v = head[u]; v != 0; v = next[v])
  52. dfs(depth+1, v);
  53. }
  54. }
  55. long long count() { // 统计
  56. ans = 0;
  57. dfs(0, 0);
  58. return ans;
  59. }
  60. } trie;
  61. const int maxl = 1000 + 10; // 每个单词最大长度
  62. int n;
  63. char word[maxl];
  64. int main() {
  65. int kase = 1;
  66. while(scanf("%d", &n) == 1 && n) {
  67. trie.clear();
  68. for(int i = 0; i < n; i++) {
  69. scanf("%s", word);
  70. trie.insert(word);
  71. }
  72. printf("Case %d: %lld\n", kase++, trie.count());
  73. }
  74. return 0;
  75. }

AC自动机

  1. // LA4670 Dominating Patterns
  2. // Rujia Liu
  3. #include<cstring>
  4. #include<queue>
  5. #include<cstdio>
  6. #include<map>
  7. #include<string>
  8. using namespace std;
  9. const int SIGMA_SIZE = 26;
  10. const int MAXNODE = 11000;
  11. const int MAXS = 150 + 10;
  12. struct AhoCorasickAutomata {
  13. int ch[MAXNODE][SIGMA_SIZE];
  14. int f[MAXNODE]; // fail函数
  15. int val[MAXNODE]; // 每个字符串的结尾结点都有一个非0的val
  16. int last[MAXNODE]; // 输出链表的下一个结点
  17. int match[MAXNODE]; // 表示这个点是结点
  18. int cnt[MAXNODE]; //用来统计模式串末尾结点被找到了几次
  19. int pos[MAXS]; //用来记录每个模式串结尾,防止多个相同模式串
  20. int sz;
  21. void init() {
  22. sz = 1;
  23. memset(ch[0], 0, sizeof(ch[0]));
  24. memset(cnt, 0, sizeof(cnt));
  25. memset(match, 0, sizeof(match));
  26. }
  27. // 字符c的编号
  28. int idx(char c) {
  29. return c-'a';
  30. }
  31. // 插入字符串。v必须非0
  32. void insert(char *s, int v) {
  33. int u = 0, n = strlen(s);
  34. for(int i = 0; i < n; i++) {
  35. int c = idx(s[i]);
  36. if(!ch[u][c]) {
  37. memset(ch[sz], 0, sizeof(ch[sz]));
  38. val[sz] = 0;
  39. ch[u][c] = sz++;
  40. }
  41. u = ch[u][c];
  42. }
  43. val[u] = v;
  44. }
  45. // 递归打印以结点j结尾的所有字符串
  46. void print(int j) {
  47. if(j) {
  48. cnt[j]++;
  49. //match[j] = 1;
  50. print(last[j]);
  51. }
  52. }
  53. // 在T中找模板
  54. int find(char* T) {
  55. int n = strlen(T);
  56. int j = 0; // 当前结点编号,初始为根结点
  57. for(int i = 0; i < n; i++) { // 文本串当前指针
  58. int c = idx(T[i]);
  59. j = ch[j][c];
  60. if(val[j]) print(j);
  61. else if(last[j]) print(last[j]); // 找到了!
  62. }
  63. }
  64. // 计算fail函数
  65. void getFail() {
  66. queue<int> q;
  67. f[0] = 0;
  68. // 初始化队列
  69. for(int c = 0; c < SIGMA_SIZE; c++) {
  70. int u = ch[0][c];
  71. if(u) { f[u] = 0; q.push(u); last[u] = 0; }
  72. }
  73. // 按BFS顺序计算fail
  74. while(!q.empty()) {
  75. int r = q.front(); q.pop();
  76. for(int c = 0; c < SIGMA_SIZE; c++) {
  77. int u = ch[r][c];
  78. if(!u) {ch[r][c] = ch[f[r]][c];continue;}
  79. q.push(u);
  80. int v = f[r];
  81. while(v && !ch[v][c]) v = f[v];
  82. f[u] = ch[v][c];
  83. last[u] = val[f[u]] ? f[u] : last[f[u]];
  84. }
  85. }
  86. /* *when Matrix need
  87. for(int i = 0; i < sz; i++) {
  88. if(val[i]) print(i);
  89. else if(last[i]) print(i);
  90. }
  91. */
  92. /* 统计长度为n的串有多种可能不出现模板串,需要Matrix
  93. int doit(int n) {
  94. matrix A(sz, sz);
  95. for(int i = 0; i < sz; i++) {
  96. if(match[i]) continue;
  97. for(int c = 0; c < SIGMA_SIZE; c++) {
  98. if(!match[ch[i][c]]) A[i][ch[i][c]]++;
  99. }
  100. }
  101. A = A ^ n;
  102. int ans = 0;
  103. for(int i = 0; i < sz; i++) {
  104. ans += A[0][i];
  105. ans %= MOD;
  106. }
  107. return ans;
  108. }
  109. */
  110. }
  111. }ac;
  112. char text[1000001], P[151][80];
  113. int n, T;
  114. int main() {
  115. while(scanf("%d", &n) == 1 && n) {
  116. ac.init();
  117. for(int i = 1; i <= n; i++) {
  118. scanf("%s", P[i]);
  119. ac.insert(P[i], i);
  120. }
  121. ac.getFail();
  122. scanf("%s", text);
  123. ac.find(text);
  124. for(int i = 1; i <= n; i++)
  125. printf("%s %d\n",P[i],ac.cnt[pos[i]]);
  126. }
  127. return 0;
  128. }

后缀数组

  1. /*
  2. 后缀数组 DA(倍增)算法求 SA[N] 与 Rank[N] (时间O(NlogN),空间O(N))
  3. sa[i] : 表示 排在第i位的后缀 起始下标
  4. rank[i] : 表示后缀 suffix(i)排在第几
  5. height[i] : 表示 sa[i-1] 与 sa[i] 的LCP 值
  6. h[i]: 表示 suffix(i)与其排名前一位的 LCP值
  7. */
  8. const int N = 100005;
  9. int wa[N],wb[N],wv[N],ws[N];
  10. int cmp(int *r,int a,int b,int l){
  11. return r[a]==r[b]&&r[a+l]==r[b+l];
  12. }
  13. void da(int *r,int *sa,int n,int m){
  14. int i,j,p,*x=wa,*y=wb;
  15. // 下面四行是对第一个字母的一个基数排序:基数排序其实就是记录前面有多少个位置被占据了
  16. for(i=0;i<m;i++) ws[i]=0; // 将统计字符数量的数组清空
  17. for(i=0;i<n;i++) ws[x[i]=r[i]]++; // 统计各种字符的个数
  18. for(i=1;i<m;i++) ws[i]+=ws[i-1]; // 进行一个累加,因为前面的小字符集对后面字符的排位有位置贡献
  19. for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i; // 根据位置来排序,sa[x] = i,表示i位置排在第x位
  20. // wa[x[i]]就是字符集0-x[i]共有多少字符占据了位置,减去自己的一个位置剩下的就是自己的排名了,排名从0开始
  21. // 排名过程中主要的过程是对于处于相同字符的字符的排序,因为改变wa[x[i]]值得只会是本身,小于该字符的贡献值
  22. // 是不变的,对于第一个字符相同的依据是位置关系,在后面将看到通过第二个关键字来确定相同字符的先后关系
  23. // 这以后的排序都是通过两个关键字来确定一个串的位置,也即倍增思想
  24. // 通过将一个串分解成两部分,而这两部分的位置关系我们都已经计算出来
  25. for(j=1,p=1;p<n;j*=2,m=p)
  26. {
  27. for(p=0,i=n-j;i<n;i++) y[p++]=i; // 枚举的串是用于与i位置的串进行合并,由于i较大,因为匹配的串为空串
  28. // 由于枚举的是长度为j的串,那么i位置开始的串将凑不出这个长度的串,因此第二关键字应该最小,这其中位置靠前的较小
  29. for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; // sa[i]-j开头的串作为第二关键字与编号为sa[i]的串匹配,sa[i]<j的串不用作为第二关键字来匹配
  30. for(i=0;i<n;i++) wv[i]=x[y[i]]; // 取出这些位置的第一关键字
  31. for(i=0;i<m;i++) ws[i]=0;
  32. for(i=0;i<n;i++) ws[wv[i]]++;
  33. for(i=1;i<m;i++) ws[i]+=ws[i-1];
  34. for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i]; // 按照第二关键字进行第一关键字的基数排序
  35. for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++) // 对排好序的sa数组进行一次字符集缩小、常数优化
  36. x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
  37. }
  38. return;
  39. }
  40. int rank[N],height[N];
  41. void calheight(int *r,int *sa,int n){ // 这里的n是原串的本来长度,即不包括新增的0
  42. int i,j,k=0;
  43. for(i=1;i<=n;i++) rank[sa[i]]=i; // 有后缀数组得到名次数组,排名第0的后缀一定是添加的0
  44. for(i=0;i<n;height[rank[i++]]=k) // 以 i 开始的后缀总能够从以 i-1 开始的后缀中继承 k-1 匹配项出来
  45. for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); //进行一个暴力的匹配,但是整个算法的时间复杂度还是O(n)的
  46. return;
  47. }
  48. DC3 模板 ( 时间复杂度O(N),空间复杂度O(3N) )
  49. const int maxn = int(3e6)+10;
  50. const int N = maxn;
  51. #define F(x) ((x)/3+((x)%3==1?0:tb))
  52. #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
  53. int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
  54. int c0(int *r,int a,int b)
  55. {return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
  56. int c12(int k,int *r,int a,int b)
  57. {if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
  58. else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}
  59. void sort(int *r,int *a,int *b,int n,int m){
  60. int i;
  61. for(i=0;i<n;i++) wv[i]=r[a[i]];
  62. for(i=0;i<m;i++) ws[i]=0;
  63. for(i=0;i<n;i++) ws[wv[i]]++;
  64. for(i=1;i<m;i++) ws[i]+=ws[i-1];
  65. for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
  66. return;
  67. }
  68. void dc3(int *r,int *sa,int n,int m){ //涵义与DA 相同
  69. int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
  70. r[n]=r[n+1]=0;
  71. for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
  72. sort(r+2,wa,wb,tbc,m);
  73. sort(r+1,wb,wa,tbc,m);
  74. sort(r,wa,wb,tbc,m);
  75. for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
  76. rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
  77. if(p<tbc) dc3(rn,san,tbc,p);
  78. else for(i=0;i<tbc;i++) san[rn[i]]=i;
  79. for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
  80. if(n%3==1) wb[ta++]=n-1;
  81. sort(r,wb,wa,ta,m);
  82. for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
  83. for(i=0,j=0,p=0;i<ta && j<tbc;p++)
  84. sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
  85. for(;i<ta;p++) sa[p]=wa[i++];
  86. for(;j<tbc;p++) sa[p]=wb[j++];
  87. return;
  88. }

SAM

最长公共子串O(n)

  1. //后缀自动机求最长公共子串,复杂度O(n)
  2. const int maxn = 250010;
  3. const int SIGMA_SIZE = 26;
  4. struct SAM_Node{
  5. SAM_Node *par,*Next[SIGMA_SIZE];
  6. int len,id,pos;
  7. SAM_Node(){}
  8. SAM_Node(int _len){
  9. par = 0;
  10. len = _len;
  11. memset(Next, 0, sizeof(Next));
  12. }
  13. };
  14. SAM_Node node[maxn*2],*root,*last;
  15. int SAM_size;
  16. SAM_Node *newSAM_Node(int len){
  17. node[SAM_size] = SAM_Node(len);
  18. node[SAM_size].id = SAM_size;
  19. return &node[SAM_size++];
  20. }
  21. SAM_Node *newSAM_Node(SAM_Node *p){
  22. node[SAM_size] = *p;
  23. node[SAM_size].id = SAM_size;
  24. return &node[SAM_size++];
  25. }
  26. void SAM_init(){
  27. SAM_size = 0;
  28. root=last = newSAM_Node(0);
  29. node[0].pos = 0;
  30. }
  31. void SAM_add(int x,int len){
  32. SAM_Node *p = last, *np = newSAM_Node(p->len+1);
  33. np->pos = len;
  34. last = np;
  35. while(p&&!p->Next[x]){
  36. p->Next[x] = np;
  37. p = p->par;
  38. }
  39. if(!p){
  40. np->par = root;
  41. return;
  42. }
  43. SAM_Node *q=p->Next[x];
  44. if(q->len == p->len+1){
  45. np->par = q;
  46. return ;
  47. }
  48. SAM_Node *nq=newSAM_Node(q);
  49. nq->len = p->len+1;
  50. q->par = nq;
  51. np->par = nq;
  52. while(p&&p->Next[x] == q){
  53. p->Next[x]=nq;
  54. p=p->par;
  55. }
  56. }
  57. void SAM_build(char *s){
  58. SAM_init();
  59. int le = strlen(s);
  60. for(int i = 0; i < le; i++) SAM_add(s[i]-'a', i+1);
  61. }
  62. int solve(char* str1,char* str2,int x){
  63. SAM_build(str1);
  64. SAM_Node *tmp=root;
  65. int le = strlen(str2);
  66. int cnt = 0, ans = 0;
  67. for(int i=0;i<le;i++){
  68. int c = str2[i] - 'a';
  69. if (tmp->Next[c]) tmp = tmp->Next[c],cnt++;
  70. else{
  71. while(tmp && !tmp->Next[c]) tmp = tmp->par;
  72. if (!tmp) tmp = root,cnt=0;
  73. else{
  74. cnt = tmp->len+1;
  75. tmp = tmp->Next[c];
  76. }
  77. }
  78. ans = max(ans, cnt); //cnt为str2以第i位为结尾与str1的最长公共子串
  79. }
  80. return ans;
  81. }

数据结构

st表

nlogn 区间rmq,只有查询没有修改

  1. int st[N][K], a[N], log_2[N];
  2. inline void ini_st(){
  3. log_2[1] = 0;
  4. for(int i = 2; i <= n; ++i){
  5. log_2[i] = log_2[i-1];
  6. if((1<<log_2[i]+1) == i) ++log_2[i];
  7. }
  8. for(int i = n; i; --i){
  9. st[i][0] = a[i];
  10. for(int j = 1; (i+(1<<j)-1) <= n; ++j)
  11. st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
  12. }
  13. }
  14. inline int ask(int l,int r){
  15. int k = log_2[r-l+1];
  16. return max(st[l][k], st[r-(1<<k)+1][k]);
  17. }

树状数组(逆序对)

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 1e5 + 7;
  7. struct binaryIndexTree{
  8. int val[N], n;
  9. inline void init(int n){
  10. this->n = n;
  11. memset(val, 0, sizeof(val));
  12. }
  13. inline void add(int k, int num){
  14. for (;k <= n; k += k&-k) val[k] += num;
  15. }
  16. int sum(int k){
  17. int sum = 0;
  18. for (; k; k -= k&-k) sum += val[k];
  19. return sum;
  20. }
  21. int Getsum(LL x1,LL x2){ //求任意区间和
  22. return sum(x2) - sum(x1-1);
  23. }
  24. } T;
  25. int arr[N], n;
  26. int main(){
  27. //freopen("in.txt", "r", stdin);
  28. for (; ~scanf("%d", &n);){
  29. T.init(n);
  30. int sum = 0;
  31. for (int i = 0; i < n; i++){
  32. scanf("%d", &arr[i]);
  33. arr[i]++;
  34. sum += T.sum(n) - T.sum(arr[i] - 1);
  35. T.add(arr[i], 1);
  36. }
  37. int ans = sum;
  38. for (int i = 0; i < n; i++){
  39. sum += (n - arr[i]) - (arr[i] - 1);
  40. ans = min(ans, sum);
  41. }
  42. printf("%d\n", ans);
  43. }
  44. }

二维树状数组

Codeforces 869E

题意:在一个n×m的方格板上,操作1将一个矩形区域的边界上加上一圈障碍,操作2将一个矩形区域的边界上的障碍移除,操作3询问两点是否能不越过障碍互相到达。题目保证任意两圈矩形障碍不会相交。
思路:很容易想到二维树状数组实现区间更新点查询,但是如果只是简单的+1,-1更新的话是无法判断出两点是否可以不经过障碍可达的。因此我们要把每一圈障碍都哈希出一个不同的值,这样点查询的时候只要判断两个点的值是否相同就行了。

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define lowbit(x) (x & -x)
  4. #define MAXN 2525
  5. using namespace std;
  6. ll bit[MAXN][MAXN];
  7. int n, m;
  8. void add(int i, int j, ll delta){
  9. for(int x = i; x < n + 10; x += lowbit(x))
  10. for(int y = j; y < m + 10; y += lowbit(y))
  11. bit[x][y] += delta;
  12. }
  13. ll sum(int i, int j){
  14. ll ans = 0;
  15. for(int x = i; x; x -= lowbit(x))
  16. for(int y = j; y; y -= lowbit(y))
  17. ans += bit[x][y];
  18. return ans;
  19. }
  20. void update(int r1, int c1, int r2, int c2, ll delta){
  21. add(r1, c1, delta);
  22. add(r1, c2 + 1, -delta);
  23. add(r2 + 1, c1, -delta);
  24. add(r2 + 1, c2 + 1, delta);
  25. }
  26. int main(){
  27. int q, t, r1, c1, r2, c2;
  28. cin >> n >> m >> q;
  29. while(q--){
  30. scanf("%d %d %d %d %d", &t, &r1, &c1, &r2, &c2);
  31. if(t != 3){
  32. ll delta = r1;
  33. delta = delta * 111 + c1;
  34. delta = delta * 111 + r2;
  35. delta = delta * 111 + c2;
  36. delta *= (t == 1) ? 1 : -1;
  37. update(r1, c1, r2, c2, delta);
  38. }
  39. else puts(sum(r1, c1) == sum(r2, c2) ? "Yes" : "No");
  40. }
  41. return 0;
  42. }

ZKW线段树(单点修改)

线段树M的计算M = (1 << (int)(ceil)(log(i)/log(2))) - 1,就不一个一个改了

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 2e5 + 7;
  7. struct segmentTree{
  8. #define lc (t<<1)
  9. #define rc (t<<1^1)
  10. int sum[N], M;
  11. inline void build(int n){
  12. M = (1 << (int)(ceil)(log(i)/log(2))) - 1;
  13. memset(sum, sizeof(sum), 0);
  14. for (int i = 1+M; i <= n+M; i++){
  15. scanf("%d", &sum[i]);
  16. }
  17. for (int t = M; t >= 1; t--){
  18. sum[t] = sum[lc] + sum[rc];
  19. }
  20. }
  21. void add(int t, int x){
  22. for (sum[t+=M]+=x, t>>=1; t; t>>=1){
  23. sum[t] = sum[lc] + sum[rc];
  24. }
  25. }
  26. int query(int l, int r){
  27. int ans = 0;
  28. for (l+=M-1,r+=M+1; l^r^1; l>>=1,r>>=1){
  29. if (~l&1) ans += sum[l^1];
  30. if ( r&1) ans += sum[r^1];
  31. }
  32. return ans;
  33. }
  34. } T;

ZKW线段树(RMQ区间操作)

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. typedef long long LL;
  7. const int N = 2e5 + 10;
  8. double EPS = 1e-11;
  9. const LL INF = 0x3f3f3f3f3f3f3f3f;
  10. int n, pos[N], arr[N], pre[N];
  11. struct ZKWsegTree{
  12. double tree[N];
  13. int M, n;
  14. void build(int n, double Mid){
  15. this->n = n;
  16. M = 1; while (M < n) M <<= 1; if (M!=1) M--;
  17. for (int t = 1 ; t <= n; t++) tree[t+M] = 1.0*t*Mid;
  18. for (int t = n+1; t <= M+1; t++) tree[t+M] = INF;
  19. for (int t = M; t >= 1; t--) tree[t] = min(tree[t<<1], tree[t<<1^1]);
  20. for (int t = 2*M+1; t >= 1; t--) tree[t] = tree[t] - tree[t>>1];
  21. }
  22. void update(int l, int r, double val){
  23. double tmp;
  24. for (l+=M-1, r+=M+1; l^r^1; l>>=1, r>>=1){
  25. if (~l&1) tree[l^1] += val;
  26. if ( r&1) tree[r^1] += val;
  27. if (l > 1) tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
  28. if (r > 1) tmp = min(tree[r], tree[r^1]), tree[r]-=tmp, tree[r^1]-=tmp, tree[r>>1]+=tmp;
  29. }
  30. for (; l > 1; l >>= 1){
  31. tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
  32. }
  33. tree[1] += tree[0], tree[0] = 0;
  34. }
  35. double query(int l, int r){
  36. double lAns = 0, rAns = 0;
  37. l += M, r += M;
  38. if (l != r){
  39. for (; l^r^1; l>>=1, r>>=1){
  40. lAns += tree[l], rAns += tree[r];
  41. if (~l&1) lAns = min(lAns, tree[l^1]);
  42. if ( r&1) rAns = min(rAns, tree[r^1]);
  43. }
  44. }
  45. double ans = min(lAns + tree[l], rAns + tree[r]);
  46. for (;l > 1;) ans += tree[l>>=1];
  47. return ans;
  48. }
  49. } T;

常规线段树(区间操作区间和)

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. typedef long long LL;
  7. const LL N = 5e5 + 7;
  8. struct segTree{
  9. #define lc (rt<<1)
  10. #define rc (rt<<1^1)
  11. #define lson l, m, rt<<1
  12. #define rson m+1, r, rt<<1^1
  13. LL M, sum[N], tag[N];
  14. inline void build(LL n){
  15. M = 1; while(M<n) M<<=1; if (M!=1) M--;
  16. memset(tag, 0, sizeof(tag));
  17. for (LL leaf = M+1; leaf <= n+M; leaf++) scanf("%lld", &sum[leaf]);
  18. for (LL leaf = n+1+M; leaf <= (M<<1^1); leaf++) sum[leaf] = 0;
  19. for (LL rt = M; rt >= 1; rt--) sum[rt] = sum[lc] + sum[rc];
  20. }
  21. inline void pushUp(LL rt){
  22. sum[rt] = sum[lc] + sum[rc];
  23. }
  24. inline void pushDown(LL rt, LL len){
  25. if (tag[rt] == 0) return;
  26. tag[lc] += tag[rt];
  27. tag[rc] += tag[rt];
  28. sum[lc] += tag[rt] * (len>>1);
  29. sum[rc] += tag[rt] * (len>>1);
  30. tag[rt] = 0;
  31. }
  32. inline void update(LL L, LL R, LL x, LL l, LL r, LL rt){
  33. //printf("update(%d, %d, %d, %d, %d, %d)\n", L, R, x, l, r, rt);
  34. if (L <= l && r <= R){
  35. tag[rt] += x;
  36. sum[rt] += (r-l+1) * x;
  37. return;
  38. }
  39. pushDown(rt, r-l+1);
  40. LL m = (l + r) >> 1;
  41. if (L <= m) update(L, R, x, lson);
  42. if (m < R) update(L, R, x, rson);
  43. pushUp(rt);
  44. }
  45. LL query(LL L, LL R, LL l, LL r, LL rt){
  46. if (L <= l && r <= R) return sum[rt];
  47. pushDown(rt, r-l+1);
  48. LL m = (l + r) >> 1;
  49. LL ans = 0;
  50. if (L <= m) ans += query(L, R, lson);
  51. if (m < R) ans += query(L, R, rson);
  52. return ans;
  53. }
  54. } T;

线段树的某些考点

双标记线段树+区间合并

hdu3397,int main 这里没贴,傻子都能写出来

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. const int N = 262144 + 7;
  8. int arr[N];
  9. // 0: 将区间[a,b]之间的数全部置为0
  10. // 1: 将区间[a,b]之间的数全部置为1
  11. // 2: 将区间[a,b]之间的 1->0 0->1
  12. // 3: 求区间[a,b]之间1的个数
  13. // 4: 求区间[a,b]之间1的最长连续长度
  14. struct segTree{
  15. #define lc (rt<<1)
  16. #define rc (rt<<1^1)
  17. #define lson l, m, rt<<1
  18. #define rson m+1, r, rt<<1^1
  19. int M; // number of no-leaf nodes
  20. int lsum[N][2], msum[N][2], rsum[N][2], nsum[N]; // values
  21. int vert[N], lazy[N]; // tags
  22. // 赋值操作,结束后记得清空vert标记
  23. inline void setTag(const int &rt, const int &val, const int &len){
  24. nsum[rt] = val ? len : 0;
  25. lsum[rt][0] = msum[rt][0] = rsum[rt][0] = val ? 0 : len;
  26. lsum[rt][1] = msum[rt][1] = rsum[rt][1] = val ? len : 0;
  27. lazy[rt] = val;
  28. vert[rt] = 0;
  29. }
  30. // 对rt节点进行取反操作,swap 0 和 1 的值
  31. inline void vertTag(const int &rt, const int &len){
  32. nsum[rt] = len - nsum[rt];
  33. swap(lsum[rt][0], lsum[rt][1]);
  34. swap(msum[rt][0], msum[rt][1]);
  35. swap(rsum[rt][0], rsum[rt][1]);
  36. vert[rt] ^= 1;
  37. }
  38. //区间合并的pushUp大体都这么写
  39. inline void pushUp(const int &rt, const int &len){
  40. nsum[rt] = nsum[lc] + nsum[rc];
  41. for (int i = 0; i < 2; i++){
  42. lsum[rt][i] = lsum[lc][i];
  43. rsum[rt][i] = rsum[rc][i];
  44. if (lsum[rt][i] == len>>1) lsum[rt][i] += lsum[rc][i];
  45. if (rsum[rt][i] == len>>1) rsum[rt][i] += rsum[lc][i];
  46. msum[rt][i] = max(msum[lc][i], msum[rc][i]);
  47. msum[rt][i] = max(msum[rt][i], rsum[lc][i] + lsum[rc][i]);
  48. }
  49. }
  50. // 优先lazy标记,但是不要干扰vert标记
  51. // vert的时候进入vertTag必须保证lazy==-1
  52. inline void pushDown(const int &rt, const int &len){
  53. if (lazy[rt] != -1){
  54. setTag(lc, lazy[rt], len>>1);
  55. setTag(rc, lazy[rt], len>>1);
  56. vert[lc] = vert[rc] = 0;
  57. }
  58. if (vert[rt]){
  59. if (lazy[lc] != -1) setTag(lc, lazy[lc]^1, len>>1);
  60. else vertTag(lc, len>>1);
  61. if (lazy[rc] != -1) setTag(rc, lazy[rc]^1, len>>1);
  62. else vertTag(rc, len>>1);
  63. vert[rt] = 0;
  64. }
  65. lazy[rt] = -1;
  66. }
  67. inline void build(const int &n){
  68. M=1; for(;M<n;) M<<=1; if(M>1)M--;
  69. memset(vert, 0, sizeof vert);
  70. memset(lazy,-1, sizeof lazy);
  71. for (int i = 1; i <= M+1; i++){
  72. nsum[i+M] = i<=n ? arr[i] : 0;
  73. lsum[i+M][0] = msum[i+M][0] = rsum[i+M][0] = i<=n ?!arr[i] : 0;
  74. lsum[i+M][1] = msum[i+M][1] = rsum[i+M][1] = i<=n ? arr[i] : 0;
  75. }
  76. for (int rt = M, len = 2; rt >= 1; rt--) {
  77. pushUp(rt, len);
  78. if ((rt&(rt-1)) == (!rt)) len <<= 1;//O(1)判断2的整数次幂,dep--
  79. }
  80. }
  81. void update(int L, int R, int val, int l, int r, int rt){
  82. if (L <= l && r <= R){
  83. if (val != -1) setTag(rt, val, r-l+1);
  84. else { // invert
  85. if (lazy[rt] != -1) setTag(rt, lazy[rt]^1, r-l+1);
  86. else vertTag(rt, r-l+1);
  87. }
  88. return;
  89. }
  90. pushDown(rt, r-l+1);
  91. int m = (l + r) >> 1;
  92. if (L <= m) update(L, R, val, lson);
  93. if (m < R) update(L, R, val, rson);
  94. pushUp(rt, r-l+1);
  95. }
  96. int sum(int L, int R, int l, int r, int rt){
  97. if (L <= l && r <= R) return nsum[rt];
  98. pushDown(rt, r-l+1);
  99. int m = (l + r) >> 1, ans = 0;
  100. if (L <= m) ans += sum(L, R, lson);
  101. if (m < R) ans += sum(L, R, rson);
  102. return ans;
  103. }
  104. int query(int L, int R, int l, int r, int rt){
  105. if (L <= l && r <= R) return msum[rt][1];
  106. pushDown(rt, r-l+1);
  107. int m = (l + r) >> 1;
  108. // 区间合并的查询操作
  109. int ans = min(m-L+1, rsum[lc][1]) + min(R - m, lsum[rc][1]);
  110. if (L <= m) ans = max(ans, query(L, R, lson));
  111. if (m < R) ans = max(ans, query(L, R, rson));
  112. return ans;
  113. }
  114. // have relation with int main, out API
  115. inline void setval(const int &l, const int &r, const int &val){
  116. update(l, r, val, 1, M+1, 1);
  117. }
  118. inline void invert(const int &l, const int &r){
  119. update(l, r, -1, 1, M+1, 1);
  120. }
  121. inline int sum(const int &l, const int &r){
  122. return sum(l, r, 1, M+1, 1);
  123. }
  124. inline int query(const int &l, const int &r){ // continus
  125. return query(l, r, 1, M+1, 1);
  126. }
  127. } T;

扫描线: 矩形面积并

HDU 1542

  1. struct Seg{
  2. double l, r, h; // height
  3. int s; // status
  4. Seg(){}
  5. Seg(double x, double y, double z, int w): l(x), r(y), h(z), s(w){}
  6. bool operator < (const Seg & b) const {return h < b.h;}
  7. } seg[N];
  8. double ux[N];
  9. int X, S; // top of seg[] & ux[]
  10. struct segTree{
  11. #define lc (rt<<1)
  12. #define rc (rt<<1^1)
  13. #define lson l, m, rt<<1
  14. #define rson m+1, r, rt<<1^1
  15. int cnt[N];
  16. double sum[N];
  17. inline void build(){
  18. memset(sum, 0, sizeof sum);
  19. memset(cnt, 0, sizeof cnt);
  20. }
  21. inline void pushUp(int rt, int l, int r){
  22. if (cnt[rt]) sum[rt] = ux[r+1] - ux[l];
  23. else sum[rt] = l==r ? 0 : sum[lc] + sum[rc];
  24. }
  25. void update(int L, int R, int x, int l, int r, int rt){
  26. if (L <= l && r <= R){
  27. cnt[rt] += x;
  28. pushUp(rt, l, r);
  29. return;
  30. }
  31. LL m = (l + r) >> 1;
  32. if (L <= m) update(L, R, x, lson);
  33. if (m < R) update(L, R, x, rson);
  34. pushUp(rt, l, r);
  35. }
  36. } T;
  37. int Search(double key, int l, int r, double ux[]){
  38. for (; l <= r;){
  39. int m = (l + r) >> 1;
  40. if (ux[m] == key) return m;
  41. if (ux[m] < key) l = m + 1;
  42. else r = m -1;
  43. }
  44. return -1;
  45. }
  46. int main(){
  47. //freopen("in.txt", "r", stdin);
  48. for (int n, _ = 1; ~scanf("%d", &n) && n;){
  49. printf("Test case #%d\n", _++);
  50. X = S = 0;
  51. for (int i = 1; i <= n; i++){
  52. double l, low, r, high;
  53. scanf("%lf%lf%lf%lf", &l, &low, &r, &high);
  54. ux[++X] = l; ux[++X] = r;
  55. seg[++S] = Seg(l, r, low, 1);
  56. seg[++S] = Seg(l, r, high, -1);
  57. }
  58. sort(seg + 1, seg + S+1);
  59. sort(ux + 1, ux + X+1);
  60. X = unique(ux + 1, ux + X +1) - ux - 1;
  61. T.build();
  62. #define root 0, X+1, 1
  63. double ans = 0;
  64. for (int i = 1; i < S; i++){
  65. int l = Search(seg[i].l, 1, X, ux);
  66. int r = Search(seg[i].r, 1, X, ux) - 1;
  67. if (l <= r) T.update(l, r, seg[i].s, root);
  68. ans += T.sum[1] * (seg[i+1].h - seg[i].h);
  69. }
  70. printf("Total explored area: %.2lf\n\n", ans);
  71. }
  72. return 0;
  73. }

扫描线, 矩形周长并

  1. int M, cnt[N], num[N], len[N];
  2. bool lbd[N], rbd[N];
  3. inline void pushUp(int rt, int l, int r){
  4. if (cnt[rt]) {
  5. lbd[rt] = rbd[rt] = 1;
  6. len[rt] = r - l + 1;
  7. num[rt] = 2;
  8. } else if (l == r) {
  9. len[rt] = num[rt] = lbd[rt] = rbd[rt] = 0;
  10. } else {
  11. lbd[rt] = lbd[lc];
  12. rbd[rt] = rbd[rc];
  13. len[rt] = len[lc] + len[rc];
  14. num[rt] = num[lc] + num[rc];
  15. if (lbd[rc] && rbd[lc]) num[rt] -= 2;
  16. }
  17. }
  18. //calc
  19. sort(seg + 1, seg + S+1);
  20. int ans = 0, last = 0;
  21. for (int i = 1; i <= S; i++, last = T.len[1]){
  22. T.update(seg[i].l, seg[i].r-1, seg[i].s, L, R-1, 1);
  23. ans += T.num[1] * (seg[i+1].h - seg[i].h);
  24. ans += abs(T.len[1] - last);
  25. }

主席树

poj2104求区间k大值

  1. # include <cstdio>
  2. # include <cstring>
  3. # include <iostream>
  4. # include <algorithm>
  5. using namespace std;
  6. const int N = 1e5 + 7;
  7. int arr[N]; //arr[] 原数组的数在rank[]中的位置;
  8. int Rank[N]; //rank[] 原数组离散化
  9. struct ChairTree{
  10. #define sum(x) tree[x].w
  11. #define lson tree[rt].lc, tree[rt1].lc, l, m
  12. #define rson tree[rt].rc, tree[rt1].rc, m+1, r
  13. struct node{
  14. int lc, rc, w;
  15. node(){}
  16. } tree[N * 20];
  17. int root[N], cnt;
  18. void build(){
  19. root[0] = cnt = 0;
  20. memset(tree, 0, sizeof(tree));
  21. }
  22. void add(int pos, int val, int &rt, int rt1, int l, int r){
  23. tree[rt = ++cnt] = tree[rt1];
  24. tree[rt].w += val;
  25. if (l == r) return;
  26. int m = (l + r) >> 1;
  27. if (pos <= m) add(pos, val, lson);
  28. else add(pos, val, rson);
  29. }
  30. //单点查询
  31. int query(int k, int rt, int rt1, int l, int r){
  32. if (l == r) return l;
  33. int lsize = sum(tree[rt1].lc) - sum(tree[rt].lc);
  34. int m = (l + r) >> 1;
  35. if (lsize >= k) return query(k, lson);
  36. else return query(k - lsize, rson);
  37. }
  38. //区间查询
  39. LL query(int L, int R, int rt, int rt1, int l, int r){
  40. if (L <= l && r <= R) return sum(rt1) - sum(rt);
  41. if (sum(rt1) == sum(rt)) return 0;
  42. LL ans = 0;
  43. int m = (l + r) >> 1;
  44. if (L <= m) ans += query(L, R, lson);
  45. if (m < R) ans += query(L, R, rson);
  46. return ans;
  47. }
  48. } T;
  49. int main(){
  50. //freopen("in.txt","r",stdin);
  51. int _, l, r, k, n, q;
  52. for (; ~scanf("%d%d", &n, &q);){
  53. T.build();
  54. for (int i = 1; i <= n; i++) {
  55. scanf("%d", &arr[i]);
  56. Rank[i] = arr[i];
  57. }
  58. sort(Rank + 1, Rank + n+1);//Rank存储原值
  59. int m = unique(Rank + 1, Rank + n +1) - (Rank + 1);//这个m很重要,WA一天系列
  60. for (int i = 1; i <= n; i++) {//离散化后的数组,仅仅用来更新
  61. arr[i] = lower_bound(Rank + 1, Rank + m+1, arr[i]) - Rank;
  62. }
  63. for (int i = 1; i <= n; i++){
  64. T.add(arr[i], 1, T.root[i], T.root[i-1], 1, m);//填m别填n
  65. }
  66. for (; q--;){
  67. scanf("%d%d%d", &l, &r, &k);
  68. int pos = T.query(k, T.root[l-1], T.root[r], 1, m);
  69. printf("%d\n", Rank[pos]);
  70. }
  71. }
  72. return 0;
  73. }

kd-Tree

解决空间最短距离的利器

  1. //Poj2648
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <climits>
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8. #define Min(a, b) ((a)<(b)?(a):(b))
  9. #define Max(a, b) ((a)>(b)?(a):(b))
  10. #define Abs(x) ((x)>0?(x):-(x))
  11. #define N 500010
  12. #define M 500010
  13. int n, m;
  14. struct Point {
  15. int x, y;
  16. Point(int _x = 0, int _y = 0):x(_x),y(_y){}
  17. void set(int _, int __) { x = _, y = __;}
  18. }P[N + M];
  19. int Dis(const Point &A, const Point &B) {
  20. return Abs(A.x - B.x) + Abs(A.y - B.y);
  21. }
  22. bool sign;
  23. inline bool cmp(const Point &A, const Point &B) {
  24. if (sign) return A.x < B.x || (A.x == B.x && A.y < B.y);
  25. else return A.y < B.y || (A.y == B.y && A.x < B.x);
  26. }
  27. struct Node {
  28. Node *l, *r;
  29. int x[2], y[2];
  30. Point p;
  31. void SetP(const Point &P) {
  32. p = P;
  33. x[0] = x[1] = P.x;
  34. y[0] = y[1] = P.y;
  35. }
  36. int Dis(const Point &p) const {
  37. int res = 0;
  38. if (p.x < x[0] || p.x > x[1])
  39. res += (p.x < x[0]) ? x[0] - p.x : p.x - x[1];
  40. if (p.y < y[0] || p.y > y[1])
  41. res += (p.y < y[0]) ? y[0] - p.y : p.y - y[1];
  42. return res;
  43. }
  44. void up(Node *B) {
  45. x[0] = Min(x[0], B->x[0]);
  46. x[1] = Max(x[1], B->x[1]);
  47. y[0] = Min(y[0], B->y[0]);
  48. y[1] = Max(y[1], B->y[1]);
  49. }
  50. } mem[N + M], *C = mem, Tnull, *null = &Tnull;
  51. Node *Build(int tl, int tr, bool d) {
  52. if (tl > tr) return null;
  53. int mid = (tl + tr) >> 1;
  54. sign = d;
  55. std::nth_element(P + tl + 1, P + mid + 1, P + tr + 1, cmp);
  56. Node *q = C++;
  57. q->SetP(P[mid]);
  58. q->l = Build(tl, mid - 1, d ^ 1);
  59. q->r = Build(mid + 1, tr, d ^ 1);
  60. if (q->l != null) q->up(q->l);
  61. if (q->r != null) q->up(q->r);
  62. return q;
  63. }
  64. #define INF 0x3f3f3f3f
  65. int res;
  66. void Ask(Node *q, const Point &p) {
  67. res = Min(res, Dis(q->p, p));
  68. int DisL = q->l != null ? q->l->Dis(p) : INF;
  69. int DisR = q->r != null ? q->r->Dis(p) : INF;
  70. if (DisL < DisR) {
  71. if (q->l != null) Ask(q->l, p);
  72. if (DisR < res && q->r != null) Ask(q->r, p);
  73. } else {
  74. if (q->r != null) Ask(q->r, p);
  75. if (DisL < res && q->l != null) Ask(q->l, p);
  76. }
  77. }
  78. void Insert(Node *root, const Point &p) {
  79. Node *q = C++;
  80. q->l = q->r = null;
  81. q->SetP(p);
  82. sign = 0;
  83. while(1) {
  84. root->up(q);
  85. if (cmp(q->p, root->p)) {
  86. if (root->l == null) {
  87. root->l = q;
  88. break;
  89. }
  90. else root = root->l;
  91. }
  92. else {
  93. if (root->r == null) {
  94. root->r = q;
  95. break;
  96. }
  97. else root = root->r;
  98. }
  99. sign ^= 1;
  100. }
  101. }
  102. int main() {
  103. scanf("%d%d", &n, &m);
  104. register int i;
  105. int ope, x, y;
  106. for(i = 1; i <= n; ++i) {
  107. scanf("%d%d", &x, &y);
  108. P[i] = Point(x, y);
  109. }
  110. Node* root = Build(1, n, 0);
  111. while(m--) {
  112. scanf("%d%d%d", &ope, &x, &y);
  113. if (ope == 1) Insert(root, Point(x, y));
  114. else {
  115. res = INF;
  116. Ask(root, Point(x, y));
  117. printf("%d\n", res);
  118. }
  119. }
  120. return 0;
  121. }

Treap

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cstdlib>
  4. #include<cassert>
  5. using namespace std;
  6. struct Node{
  7. Node *ch[2];
  8. int r, v, s;//s表示节点数
  9. Node(int v):v(v){
  10. ch[0]=ch[1]=NULL;
  11. r = rand();//在cstdlib头声明
  12. s = 1;
  13. }
  14. int cmp(int x){
  15. if (x == v) return -1;
  16. return x<v ? 0 : 1;
  17. }
  18. void maintain(){
  19. s = 1;
  20. if(ch[0]!=NULL) s+=ch[0]->s;
  21. if(ch[1]!=NULL) s+=ch[1]->s;
  22. }
  23. }; //root全局使用的话可以在这里跟上*root
  24. void rotate(Node* &o,int d){
  25. Node *k=o->ch[d^1];
  26. o->ch[d^1]=k->ch[d];
  27. k->ch[d]=o;
  28. o->maintain();
  29. k->maintain();
  30. o=k;
  31. }
  32. void insert(Node* &o,int x){//o子树中事先不存在x
  33. if(o==NULL) o=new Node(x);
  34. else{
  35. //如这里改成int d=o->cmp(x);
  36. //就不可以插入相同的值,因为d可能为-1
  37. int d=x<(o->v)?0:1;
  38. insert(o->ch[d],x);
  39. if(o->ch[d]->r > o->r)
  40. rotate(o,d^1);
  41. }
  42. o->maintain();
  43. }
  44. void remove(Node* &o,int x){
  45. if (o==NULL) return ;//空时返回
  46. int d=o->cmp(x);
  47. if (d == -1){
  48. Node *u=o;
  49. if(o->ch[0] && o->ch[1]){
  50. int d2=(o->ch[0]->r < o->ch[1]->r)?0:1;
  51. rotate(o,d2);
  52. remove(o->ch[d2],x);
  53. }else{
  54. if(o->ch[0]==NULL) o=o->ch[1];
  55. else o=o->ch[0];
  56. delete u;//这个要放里面
  57. }
  58. }
  59. else remove(o->ch[d],x);
  60. if(o) o->maintain();//之前o存在,但是删除节点后o可能就是空NULL了,所以需要先判断o是否为空
  61. }
  62. //返回关键字从小到大排序时的第k个值
  63. //若返回第K大的值,只需要把ch[0]和ch[1]全互换就可以了
  64. int kth(Node* o,int k){
  65. assert(o && k>=1 && k<=o->s);//保证输入合法,根据实际问题返回
  66. int s=(o->ch[0]==NULL)?0:o->ch[0]->s;
  67. if(k==s+1) return o->v;
  68. else if(k<=s) return kth(o->ch[0],k);
  69. else return kth(o->ch[1],k-s-1);
  70. }
  71. //返回值x在树中的排名,就算x不在o树中也能返回排名
  72. //返回值范围在[1,o->s+1]范围内
  73. int rank(Node* o,int x){
  74. if(o==NULL) return 1;//未找到x;
  75. int num= o->ch[0]==NULL ? 0:o->ch[0]->s;
  76. if(x==o->v) return num+1;
  77. else if(x < o->v) return rank(o->ch[0],x);
  78. else return rank(o->ch[1],x)+num+1;
  79. }
  80. int main(){
  81. int n=0, v;
  82. while(scanf("%d",&n)==1 && n){
  83. Node *root=NULL; //初始化为NULL
  84. for(int i=0; i<n; i++){
  85. int x;
  86. scanf("%d",&x);
  87. if(root==NULL) root=new Node(x);
  88. else insert(root,x);
  89. }
  90. while(scanf("%d",&v)==1){
  91. printf("%d\n",rank(root,v));
  92. }
  93. }
  94. return 0;
  95. }

分块

分块入门 1

给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值。

  1. int n, blo;
  2. int v[50005],bl[50005],atag[50005];
  3. void add(int a, int b, int c){
  4. for(int i=a;i<=min(bl[a]*blo,b);i++) v[i]+=c;
  5. if(bl[a]!=bl[b])
  6. for(int i=(bl[b]-1)*blo+1;i<=b;i++) v[i]+=c;
  7. for(int i=bl[a]+1;i<=bl[b]-1;i++) atag[i]+=c;
  8. }
  9. int main(){
  10. n=read(); blo=sqrt(n);
  11. for(int i=1;i<=n;i++)v[i]=read();
  12. for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;
  13. for(int i=1;i<=n;i++){
  14. int f=read(),a=read(),b=read(),c=read();
  15. if(f==0)add(a,b,c);
  16. if(f==1)printf("%d\n",v[b]+atag[bl[b]]);
  17. }
  18. return 0;
  19. }

分块入门 2

给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的元素个数。

  1. int n,blo;
  2. int v[50005], bl[50005], atag[50005];
  3. vector<int>ve[505];
  4. void reset(int x){
  5. ve[x].clear();
  6. for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++)
  7. ve[x].push_back(v[i]);
  8. sort(ve[x].begin(),ve[x].end());
  9. }
  10. void add(int a,int b,int c){
  11. for(int i=a;i<=min(bl[a]*blo,b);i++)
  12. v[i]+=c;
  13. reset(bl[a]);
  14. if(bl[a]!=bl[b]){
  15. for(int i=(bl[b]-1)*blo+1;i<=b;i++)v[i]+=c;
  16. reset(bl[b]);
  17. }
  18. for(int i=bl[a]+1;i<=bl[b]-1;i++)
  19. atag[i]+=c;
  20. }
  21. int query(int a,int b,int c){
  22. int ans=0;
  23. for(int i=a;i<=min(bl[a]*blo,b);i++)
  24. if(v[i]+atag[bl[a]]<c)ans++;
  25. if(bl[a]!=bl[b])
  26. for(int i=(bl[b]-1)*blo+1;i<=b;i++)
  27. if(v[i]+atag[bl[b]]<c)ans++;
  28. for(int i=bl[a]+1;i<=bl[b]-1;i++){
  29. int x=c-atag[i];
  30. ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin();
  31. }
  32. return ans;
  33. }
  34. int main(){
  35. n=read();blo=sqrt(n);
  36. for(int i=1;i<=n;i++)v[i]=read();
  37. for(int i=1;i<=n;i++){
  38. bl[i]=(i-1)/blo+1;
  39. ve[bl[i]].push_back(v[i]);
  40. }
  41. for(int i=1;i<=bl[n];i++)
  42. sort(ve[i].begin(),ve[i].end());
  43. for(int i=1;i<=n;i++){
  44. int f=read(),a=read(),b=read(),c=read();
  45. if(f==0)add(a,b,c);
  46. if(f==1)printf("%d\n",query(a,b,c*c));
  47. }
  48. return 0;
  49. }

分块入门 3

给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的前驱(比其小的最大元素)。

  1. int n,blo;
  2. int v[100005],bl[100005],atag[100005];
  3. set<int>st[105];
  4. void add(int a,int b,int c){
  5. for(int i=a;i<=min(bl[a]*blo,b);i++){
  6. st[bl[a]].erase(v[i]);
  7. v[i] += c;
  8. st[bl[a]].insert(v[i]);
  9. }
  10. if(bl[a]!=bl[b]){
  11. for(int i=(bl[b]-1)*blo+1;i<=b;i++){
  12. st[bl[b]].erase(v[i]);
  13. v[i] += c;
  14. st[bl[b]].insert(v[i]);
  15. }
  16. }
  17. for(int i=bl[a]+1;i<=bl[b]-1;i++)
  18. atag[i]+=c;
  19. }
  20. int query(int a,int b,int c){
  21. int ans=-1;
  22. for(int i=a;i<=min(bl[a]*blo,b);i++){
  23. int val=v[i]+atag[bl[a]];
  24. if(val<c)ans=max(val,ans);
  25. }
  26. if(bl[a]!=bl[b])
  27. for(int i=(bl[b]-1)*blo+1;i<=b;i++){
  28. int val=v[i]+atag[bl[b]];
  29. if(val<c)ans=max(val,ans);
  30. }
  31. for(int i=bl[a]+1;i<=bl[b]-1;i++){
  32. int x=c-atag[i];
  33. set<int>::iterator it=st[i].lower_bound(x);
  34. if(it==st[i].begin())continue;
  35. --it;
  36. ans=max(ans,*it+atag[i]);
  37. }
  38. return ans;
  39. }
  40. int main(){
  41. n=read();blo=1000;
  42. for(int i=1;i<=n;i++)v[i]=read();
  43. for(int i=1;i<=n;i++){
  44. bl[i]=(i-1)/blo+1;
  45. st[bl[i]].insert(v[i]);
  46. }
  47. for(int i=1;i<=n;i++){
  48. int f=read(),a=read(),b=read(),c=read();
  49. if(f==0)add(a,b,c);
  50. if(f==1)printf("%d\n",query(a,b,c));
  51. }
  52. return 0;
  53. }

左偏树

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. using namespace std;
  6. const int MAXN = 1e5 + 5;
  7. struct node{
  8. int l,r,dis,key;
  9. } tree[MAXN];
  10. int far[MAXN];
  11. int Find(int x) {
  12. if(far[x] == x) return x;
  13. return far[x] = Find(far[x]);
  14. }
  15. int merge(int a,int b){
  16. if(!a) return b;
  17. if(!b) return a;
  18. if(tree[a].key < tree[b].key) swap(a, b);//大堆
  19. tree[a].r = merge(tree[a].r,b);
  20. far[tree[a].r] = a;//并查
  21. if(tree[tree[a].l].dis < tree[tree[a].r].dis) swap(tree[a].l,tree[a].r);
  22. if(tree[a].r)tree[a].dis = tree[tree[a].r].dis + 1;
  23. else tree[a].dis = 0;
  24. return a;
  25. }
  26. int pop(int a){
  27. int l = tree[a].l;
  28. int r = tree[a].r;
  29. far[l] = l;//因为要暂时删掉根,所以左右子树先作为根
  30. far[r] = r;
  31. tree[a].l = tree[a].r = tree[a].dis = 0;
  32. return merge(l,r);
  33. }
  34. int main(){
  35. int N, M;
  36. while(cin >> N){
  37. for(int i = 1; i <= N; i++){
  38. int x;
  39. far[i] = i;
  40. scanf("%d", &x);
  41. tree[i].key = x;
  42. tree[i].l = tree[i].r = tree[i].dis = 0;
  43. }
  44. cin >> M;
  45. while(M--) {
  46. int x, y;
  47. scanf("%d%d", &x, &y);
  48. x = Find(x);
  49. y = Find(y);
  50. if(x == y) {
  51. printf("-1\n");
  52. } else {
  53. int ra = pop(x);
  54. tree[x].key /= 2;
  55. ra = merge(ra, x);
  56. int rb = pop(y);
  57. tree[y].key /= 2;
  58. rb = merge(rb, y);
  59. x = merge(ra, rb);
  60. printf("%d\n", tree[x].key);
  61. }
  62. }
  63. }
  64. return 0;
  65. }

Splay

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. struct Node{
  5. int key;//size
  6. Node *l,*r,*f;//left,right,father
  7. };
  8. class SplayTree{
  9. public:
  10. void Init(){rt=NULL;}
  11. void Zag(Node *x){//left rotate
  12. Node *y=x->f;//y is the father of x
  13. y->r = x->l;
  14. if (x->l)x->l->f = y;//if x has left child
  15. x->f =y->f;
  16. if (y->f){//y is not root
  17. if (y==y->f->l)y->f->l=x;//y if left child
  18. else y->f->r=x;//y is right child
  19. }
  20. y->f=x; x->l=y;
  21. }
  22. void Zig(Node *x){//right rotate
  23. Node *y=x->f;//y is the father of x
  24. y->l = x->r;
  25. if (x->r)x->r->f=y;
  26. x->f = y->f;
  27. if (y->f){
  28. if (y==y->f->l)y->f->l=x;
  29. else y->f->r=x;
  30. }
  31. y->f=x;
  32. x->r=y;
  33. }
  34. void Splay(Node *x){
  35. while (x->f){
  36. Node *p=x->f;
  37. if (!p->f){
  38. if (x==p->l)Zig(x);
  39. else Zag(x);
  40. }else if (x==p->l){
  41. if (p==p->f->l){Zig(p);Zig(x);}
  42. else {Zig(x);Zag(x);}
  43. }else {//x==p->r
  44. if (p==p->f->r){Zag(p);Zag(x);}
  45. else {Zag(x);Zig(x);}
  46. }
  47. }
  48. rt=x;
  49. }
  50. Node *Find(int x){
  51. Node *T=rt;
  52. while (T){
  53. if (T->key==x){Splay(T);return T;}
  54. else if (x<T->key)T=T->l;
  55. else T=T->r;
  56. }
  57. return T;
  58. }
  59. void Insert(int x){
  60. Node *T=rt,*fa=NULL;
  61. while (T){
  62. fa=T;
  63. if (x<T->key)T=T->l;
  64. else if(x>T->key)T=T->r;
  65. else return ;//two the same keys
  66. }
  67. T=(Node*)malloc(sizeof(Node));
  68. T->key=x;
  69. T->l=T->r=NULL;
  70. T->f=fa;
  71. if (fa){
  72. if (fa->key>x)fa->l=T;
  73. else fa->r=T;
  74. }
  75. Splay(T);
  76. }
  77. void Delete(int x){
  78. Node *T=Find(x);
  79. if (NULL==T)return ;//error
  80. rt=Join(T->l,T->r);
  81. }
  82. Node *Maxnum(Node *t){
  83. Node *T=t;
  84. while (T->r)T=T->r;
  85. Splay(T);
  86. return T;
  87. }
  88. Node *Minnum(Node *t){
  89. Node *T=t;
  90. while (T->l)T=T->l;
  91. Splay(T);
  92. return T;
  93. }
  94. Node *Last(int x){
  95. Node *T=Find(x);
  96. T=T->l;
  97. return (Maxnum(T));
  98. }
  99. Node *Next(int x){
  100. Node *T=Find(x);
  101. T=T->r;
  102. return (Minnum(T));
  103. }
  104. Node *Join(Node *t1,Node *t2){
  105. if (NULL==t1)return t2;
  106. if (NULL==t2)return t1;
  107. Node *T=Maxnum(t1);
  108. T->l=t2;
  109. return T;
  110. }
  111. void Split(int x,Node *&t1,Node *&t2){
  112. Node *T=Find(x);
  113. t1=T->l; t2=T->r;
  114. }
  115. void Inorder(Node *T){
  116. if (NULL==T)return ;
  117. Inorder(T->l);
  118. printf("%d->",T->key);
  119. Inorder(T->r);
  120. }
  121. void _Delete(){Delete(rt);}
  122. void Delete(Node *T){
  123. if (NULL==T)return ;
  124. Delete(T->l);
  125. Delete(T->r);
  126. free(T);
  127. }
  128. private:
  129. Node *rt;//root
  130. };

AVL树

  1. //codevs1285 莯ʕѸ˹
  2. //by cww97
  3. #include<cstdio>
  4. #include<iostream>
  5. #include<algorithm>
  6. #define INF 0xfffffff
  7. #define BASE 1000000
  8. using namespace std;
  9. int ans=0;
  10. struct Node{
  11. int x,bf,h;//bf=balance factor,h=height
  12. Node *l,*r;
  13. };
  14. class AVLTree{
  15. public:
  16. void Init() { rt = NULL; }
  17. int H(Node *T){return (T==NULL)?0:T->h;}
  18. int BF(Node *l,Node *r){//get balance factor
  19. if (NULL==l && NULL==r) return 0;
  20. else if (NULL == l) return</