快速小知识点

0.模板

https://www.luogu.org/problem/lists?name=%E6%A8%A1%E6%9D%BF

1.判数字回文

bool check(ll x) {
  ll t = x, y = 0;
  while (t) {
    y = y * 10 + t % 10;
    t /= 10;
  }
  if (x != y)
    return 0;
 return 1;
}

 2.Java高精度

http://blog.csdn.net/piaocoder/article/details/47071935

3. c++高精度

http://blog.csdn.net/code4101/article/details/23020525

// 去吧！皮卡丘! 把AC带回来！
//      へ　　　　　／|
// 　　/＼7　　　 ∠＿/
// 　 /　│　　 ／　／
// 　│　Z ＿,＜　／　　 /`ヽ
// 　│　　　　　ヽ　　 /　　〉
// 　Y　　　　　`　 /　　/
// 　ｲ●　､　●　　⊂⊃〈　　/
// 　()　 へ　　　　|　＼〈
// 　　>ｰ ､_　 ィ　 │ ／／
// 　 / へ　　 /　ﾉ＜| ＼＼
// 　 ヽ_ﾉ　　(_／　 │／／
// 　　 7　　　　　　　|／
// 　　 ＞―r￣￣`ｰ―＿
//**************************************
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template <class T> inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf("%d", &x)
#define scanf2(x, y) scanf("%d%d", &x, &y)
#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define bug printf("***********\n");
#define mp make_pair
#define pb push_back
const int maxn = 3e5 + 10;
const int maxx = 1e6 + 10;
// name*******************************
struct bign {
  int len, d[30];
  bign() {
    memset(d, 0, sizeof(d));
    len = 1;
  }
  void clean() {
    while (len > 1 && !d[len - 1])
      len--;
  }
  bign(int num) { *this = num; }
  bign(const char *num) { *this = num; }
  bign operator=(const char *num) {
    memset(d, 0, sizeof(d));
    len = strlen(num);
    For(i, 0, len - 1) d[i] = num[len - 1 - i] - '0';
    return *this;
  }
  bign operator=(int num) {
    char s[30];
    sprintf(s, "%d", num);
    *this = s;
    return *this;
  }
  bign operator+(bign b) {
    bign c = *this;
    int i;
    for (i = 0; i <= b.len - 1; i++) {
      c.d[i] += b.d[i];
      if (c.d[i] > 9) {
        c.d[i] %= 10;
        c.d[i + 1]++;
      }
    }
    while (c.d[i] > 9)
      c.d[i] %= 10, c.d[++i]++;
    c.len = max(len, b.len);
    if (c.d[i] && c.len == i)
      c.len++;
    return c;
  }

  bign operator-(bign b) {
    bign c = *this;
    int i;
    for (i = 0; i <= b.len - 1; i++) {
      c.d[i] -= b.d[i];
      if (c.d[i] < 0) {
        c.d[i] += 10;
        c.d[i + 1]--;
      }
    }
    while (c.d[i] < 0)
      c.d[i] += 10, c.d[++i]--;
      clean();
    return c;
  }

  string str() const {
    char s[30] = {};
    For(i, 0, len - 1) s[i] = d[len - 1 - i] + '0';
    return s;
  }
};
istream &operator>>(istream &in, bign &num) {
  string s;
  in >> s;
  num = s.c_str();
  return in;
}
ostream &operator<<(ostream &out, const bign &num) {
  out << num.str();
  return out;
}
// function******************************

//***************************************
int main() {
  // ios::sync_with_stdio(0); cin.tie(0);
  // freopen("test.txt", "r", stdin);
  //  freopen("outout.txt","w",stdout);
  bign a, b;
  cin >> a >> b;
  cout << a + b;
  cout << endl << a - b;

  return 0;
}

4.矩阵快速幂

#include<iostream> #include<cstring>
#define mod 1000000007
#define ll long long
using namespace std; struct mat { ll m[105][105]; }; mat a,e; ll n,p; mat mul(mat a,mat b) { mat c; memset(c.m,0,sizeof(c.m)); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) c.m[i][j]=c.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod,c.m[i][j]%=mod; return c; } mat qmul(mat a,ll b) { mat ans=e; while(b) { if(b&1) ans=mul(ans,a); a=mul(a,a); b>>=1; } return ans; } int main() { // freopen("test.txt","r",stdin);
    cin>>n>>p; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>a.m[i][j]; for(int i=1; i<=n; i++)e.m[i][i]=1; mat ans=qmul(a,p); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) cout<<ans.m[i][j]%mod<<" "; cout<<endl; } return 0; }

https://www.luogu.org/problemnew/show/P3390

http://blog.csdn.net/wust_zzwh/article/details/52058209

5.最小生成树

https://www.luogu.org/problemnew/show/P3366

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c)
{
    return min(min(a, b), c);
}
template <class T> inline T max(T a, T b, T c)
{
    return max(max(a, b), c);
}
template <class T> inline T min(T a, T b, T c, T d)
{
    return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d)
{
    return max(max(a, b), max(c, d));
}
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define mp make_pair
#define pb push_back
const int maxn = 100005;
#define mod 100003
const int N=10005;

// name*******************************
struct edge
{
    int from,to,dis;
} e[N];
int pre[N];
int Rank[N];
int tot=0;
int ans=0;
int n;
// function******************************
bool cmp(edge x,edge y)
{
    return x.dis<y.dis;
}
void init(int x)
{
    pre[x]=-1;
    Rank[x]=0;
}
int find(int x)
{
    int r=x;
    while(pre[r]!=-1)r=pre[r];
    while(x!=r)
    {
        int k=pre[x];
        pre[x]=r;
        x=k;
    }
    return r;
}
void unionone(int a,int b)
{
    int t1=find(a);
    int t2=find(b);
    if(Rank[t1]>Rank[t2])
        pre[t2]=t1;
    else pre[t1]=t2;
    if(Rank[t1]==Rank[t2])
        Rank[t2]++;
}

//***************************************
int main()
{
//         freopen("test.txt", "r", stdin);
    cin>>n;
    For(i,1,n)init(i);
    For(i,1,n)
    For(j,1,n)
    {
        int x;
        scanf("%d",&x);
        if(i!=j)
        {
            e[++tot].from=i;
            e[tot].to=j;
            e[tot].dis=x;
        }
    }
    sort(e+1,e+1+tot,cmp);
    int cnt=0;
    For(i,1,tot)
    {
        if(find(e[i].from)!=find(e[i].to))
        {
            unionone(e[i].from,e[i].to);
            ans+=e[i].dis;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    cout<<ans;


    return 0;
}

6.并查集

https://www.luogu.org/problemnew/show/P3367

// 去吧！皮卡丘! 把AC带回来！
//      へ　　　　　／|
// 　　/＼7　　　 ∠＿/
// 　 /　│　　 ／　／
// 　│　Z ＿,＜　／　　 /`ヽ
// 　│　　　　　ヽ　　 /　　〉
// 　Y　　　　　`　 /　　/
// 　ｲ●　､　●　　⊂⊃〈　　/
// 　()　 へ　　　　|　＼〈
// 　　>ｰ ､_　 ィ　 │ ／／
// 　 / へ　　 /　ﾉ＜| ＼＼
// 　 ヽ_ﾉ　　(_／　 │／／
// 　　 7　　　　　　　|／
// 　　 ＞―r￣￣`ｰ―＿
//**************************************
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template <class T> inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf("%d", &x)
#define scanf2(x, y) scanf("%d%d", &x, &y)
#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define bug printf("***********\n");
#define mp make_pair
#define pb push_back
const int maxn = 5e5 + 10;
// name*******************************
int pre[20000000];
int Rank[20000000];
int n, m;
// function******************************

void makeset(int x) {
  pre[x] = -1;
  Rank[x] = 0;
}
int find(int x) {
  int r = x;
  while (pre[r] != -1)
    r = pre[r];
  //压缩路径
  while (x != r) {
    int q = pre[x];
    pre[x] = r;
    x = q;
  }
  return r;
}
void unionone(int a, int b) {
  int t1 = find(a);
  int t2 = find(b);
if(t1==t2)return;//麻烦这句话在里面也加上，mmp无数次下面没判断导致死循环了！！！
  if (Rank[t1] > Rank[t2])
    pre[t2] = t1;
  else
    pre[t1] = t2;
  if (Rank[t1] == Rank[t2])
    Rank[t2]++;
}

//***************************************
int main() {
  ios::sync_with_stdio(0);
  // cin.tie(0);
  // freopen("test.txt", "r", stdin);
  //  freopen("outout.txt","w",stdout);
  int t, x, y;
  cin >> n >> m;
  For(i, 1, n) makeset(i);
  For(i, 1, m) {
    cin >> t >> x >> y;
    if (t == 1) {
      if (find(x) != find(y))//unionone之前一定要find找一次啊啊啊！！！
        unionone(x, y);
    } else {
      if (find(x) == find(y))
        cout << "Y";
      else
        cout << "N";
      cout << endl;
    }
  }

  return 0;
}

7.树状数组

https://www.luogu.org/problemnew/show/P3374#sub

// 去吧！皮卡丘! 把AC带回来！
//      へ　　　　　／|
// 　　/＼7　　　 ∠＿/
// 　 /　│　　 ／　／
// 　│　Z ＿,＜　／　　 /`ヽ
// 　│　　　　　ヽ　　 /　　〉
// 　Y　　　　　`　 /　　/
// 　ｲ●　､　●　　⊂⊃〈　　/
// 　()　 へ　　　　|　＼〈
// 　　>ｰ ､_　 ィ　 │ ／／
// 　 / へ　　 /　ﾉ＜| ＼＼
// 　 ヽ_ﾉ　　(_／　 │／／
// 　　 7　　　　　　　|／
// 　　 ＞―r￣￣`ｰ―＿
//**************************************
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template <class T> inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf("%d", &x)
#define scanf2(x, y) scanf("%d%d", &x, &y)
#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define bug printf("***********\n");
#define mp make_pair
#define pb push_back
const int maxn = 5e5 + 10;
// name*******************************
int n, m;
int C[maxn];

// function******************************
inline int lowbit(int x) { return x & (-x); }
void modify(int x, int v) {
  while (x <= n) {
    C[x] += v;
    x += lowbit(x);
  }
}
int get_sum(int x) {
  int res = 0;
  while (x) {
    res += C[x];
    x -= lowbit(x);
  }
  return res;
}
int query(int x, int y) { return get_sum(y) - get_sum(x - 1); }
//***************************************
int main() {
  // ios::sync_with_stdio(0); cin.tie(0);
  // freopen("test.txt", "r", stdin);
  //  freopen("outout.txt","w",stdout);
  cin >> n >> m;
  int x;
  For(i, 1, n) {
    cin >> x;
    modify(i, x);
  }
  For(i, 1, m) {
    cin >> x;
    int a, b;
    cin >> a >> b;
    if (x == 1) {
      modify(a, b);
    } else {
      cout << query(a, b) << endl;
    }
  }

  return 0;
}

https://www.luogu.org/problemnew/show/P3368

// 去吧！皮卡丘! 把AC带回来！
//      へ　　　　　／|
// 　　/＼7　　　 ∠＿/
// 　 /　│　　 ／　／
// 　│　Z ＿,＜　／　　 /`ヽ
// 　│　　　　　ヽ　　 /　　〉
// 　Y　　　　　`　 /　　/
// 　ｲ●　､　●　　⊂⊃〈　　/
// 　()　 へ　　　　|　＼〈
// 　　>ｰ ､_　 ィ　 │ ／／
// 　 / へ　　 /　ﾉ＜| ＼＼
// 　 ヽ_ﾉ　　(_／　 │／／
// 　　 7　　　　　　　|／
// 　　 ＞―r￣￣`ｰ―＿
//**************************************
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template <class T> inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf("%d", &x)
#define scanf2(x, y) scanf("%d%d", &x, &y)
#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define bug printf("***********\n");
#define mp make_pair
#define pb push_back
const int maxn = 5e5 + 10;
// name*******************************
int n, m;
int C[maxn];

// function******************************
inline int lowbit(int x) { return x & (-x); }
void modify(int x, int v) {
  while (x <= n) {
    C[x] += v;
    x += lowbit(x);
  }
}
int get_sum(int x) {
  int res = 0;
  while (x) {
    res += C[x];
    x -= lowbit(x);
  }
  return res;
}
int query(int x, int y) { return get_sum(y) - get_sum(x - 1); }
//***************************************
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("test.txt", "r", stdin);
  //  freopen("outout.txt","w",stdout);
  cin >> n >> m;
  int x, y = 0;
  For(i, 1, n) {
    cin >> x;
    modify(i, x - y);
    y = x;
  }
  For(i, 1, m) {
    cin >> x;
    if (x == 1) {
      int a, b, c;
      cin >> a >> b >> c;
      modify(a, c);
      modify(b + 1, -c);
    } else {
      int a;
      cin >> a;
      cout << get_sum(a) << endl;
    }
  }

  return 0;
}

 7.5.线段树

https://www.luogu.org/problemnew/show/P3372

递归版本

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c)
{
    return min(min(a, b), c);
}
template <class T> inline T max(T a, T b, T c)
{
    return max(max(a, b), c);
}
template <class T> inline T min(T a, T b, T c, T d)
{
    return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d)
{
    return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf("%d", &x)
#define scanf2(x, y) scanf("%d%d", &x, &y)
#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define bug printf("***********\n");
#define mp make_pair
#define pb push_back
const int N = 1000001;
const int M=200005;
// name*******************************
ll n,m,a[N],ans[N<<2],tag[N<<2];
// function******************************
inline ll ls(ll x)
{
    return x<<1;
}
inline ll rs(ll x)
{
    return x<<1|1;
}
inline void push_up(ll p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;//清空标签
    if(l==r)
    {
        ans[p]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);//从底层往上回溯
}
inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]+=k;
    ans[p]+=k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r) //向下释放
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;//过往点清空
}
inline void update(ll wl,ll wr,ll l,ll r,ll p,ll k)
{
    if(wl<=l&&r<=wr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return;
    }
    push_down(p,l,r);//更新前，先释放tag
    ll mid=(l+r)>>1;
    if(wl<=mid)update(wl,wr,l,mid,ls(p),k);
    if(wr>mid)update(wl,wr,mid+1,r,rs(p),k);
    push_up(p);//统计总和
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);//释放
    if(q_x<=mid)res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid)res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}

//***************************************
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    // freopen("test.txt", "r", stdin);
    //  freopen("outout.txt","w",stdout);
    ll a1,b,c,d,e,f;

    cin>>n>>m;
    For(i,1,n)
    scanf("%lld",&a[i]);

    build(1,1,n);
    while(m--)
    {
        scanf("%lld",&a1);
        if(a1==1)
        {
            scanf("%lld%lld%lld",&b,&c,&d);
            update(b,c,1,n,1,d);
        }
        else
        {
            scanf("%lld%lld",&e,&f);
            printf("%lld\n",query(e,f,1,n,1));
        }
    }

    return 0;
}

// #include "a.h"
#include <bits/stdc++.h>
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define re register int
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define me(a, b) memset(a, b, sizeof(a))
#define file(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
//*******************input**************************
//*************1
#define sdf(x) scanf("%d", &x)
//*************2
// char ss[1 << 17], *A = ss, *B = ss; 
// inline char gc() { return A == B && (B = (A = ss) + fread(ss, 1, 1 << 17, stdin), A == B) ? -1 : *A++; }
// template <class T>
// inline void sdf(T &x)
// {
//   char c;
//   T y = 1;
//   while (c = gc(), (c < 48 || 57 < c) && c != -1)
//     if (c == '-')
//       y = -1;
//   x = c ^ 48;
//   while (c = gc(), 47 < c && c < 58)
//     x = (x << 1) + (x << 3) + (c ^ 48);
//   x *= y;
// }
//********/input**********
template <class T>
inline T min(T a, T b, T c)
{
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c)
{
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d)
{
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d)
{
  return max(max(a, b), max(c, d));
}
using namespace std;
const int N = 1e6 + 5;
const double eps = 1e-9;
typedef int arr[N];
typedef ll aLL[N];

int n, m;
aLL sum;
arr tg, a;
ll sgt;

namespace seg
{
void build(int n)
{
  sgt = 1;
  while (sgt < n + 2)
    sgt <<= 1;
  For(i, 1, n) sum[i + sgt] = a[i];
  FFor(i, sgt - 1, 1) sum[i] = sum[i << 1] + sum[i << 1 | 1], tg[i] = 0; //注意这里是sgt-1不是n-1
}
// void mdy1(int p, ll x)
// {
//   for (ll s = p + sgt; s; s >>= 1)
//     sum[s] += x;
// }
// ll qry1(int l, int r)
// {
//   ll res = 0;
//   for (ll s = l + sgt - 1, t = r + sgt + 1; s ^ t ^ 1; s >>= 1, t >>= 1)
//   {
//     if (~s & 1)
//       res += sum[s ^ 1];
//     if (t & 1)
//       res += sum[t ^ 1];
//   }
//   return res;
// }
inline void mdyn(int l, int r, ll c)
{
  int s, t, x = 1;
  ll Ln = 0, Rn = 0;
  for (s = l + sgt - 1, t = r + sgt + 1; s ^ t ^ 1; s >>= 1, t >>= 1, x <<= 1)
  {
    //处理前一次
    sum[s] += Ln * c;
    sum[t] += Rn * c;
    if (~s & 1)
      sum[s ^ 1] += x * c, tg[s ^ 1] += c, Ln += x;
    if (t & 1)
      sum[t ^ 1] += x * c, tg[t ^ 1] += c, Rn += x;
  }
  for (; s; s >>= 1, t >>= 1)
  {
    sum[s] += Ln * c;
    sum[t] += Rn * c;
  }
}
ll qryn(int l, int r)
{
  ll res = 0;
  ll Ln = 0, Rn = 0;
  int x = 1, s, t;
  for (s = l + sgt - 1, t = r + sgt + 1; s ^ t ^ 1; s >>= 1, t >>= 1, x <<= 1)
  {
    if (tg[s])
      res += tg[s] * Ln;
    if (tg[t])
      res += tg[t] * Rn;
    if (~s & 1)
      res += sum[s ^ 1], Ln += x;
    if (t & 1)
      res += sum[t ^ 1], Rn += x;
  }
  for (; s; s >>= 1, t >>= 1)
  {
    res += Ln * tg[s];
    res += Rn * tg[t];
  }
  return res;
}
} // namespace seg

int main()
{
  // file("test");
  sdf(n), sdf(m);
  For(i, 1, n) sdf(a[i]);
  seg::build(n);

  while (m--)
  {
    int t;
    sdf(t);
    if (t == 1)
    {
      int x, y, z;
      sdf(x), sdf(y), sdf(z);
      seg::mdyn(x, y, z);
    }
    else
    {
      int x, y;
      sdf(x), sdf(y);
      printf("%lld\n", seg::qryn(x, y));
    }
  }
  // system("pause");
  return 0;
}

https://www.luogu.org/problemnew/show/P3373

 8.全排列

手写+stl

C(n,r)组合dfs

//p[]打标记
void dfs(int x,int cur)
{
    if(x==r+1)
    {
        for(int i=1; i<=r; i++)
            cout<<p[i]<<" ";
        cout<<endl;
        return;
    }
    if(x>r+1)
        return;
    if(cur>n)
        return;
    p[x]=cur;
    dfs(x+1,cur+1);
    dfs(x,cur+1);
}

    dfs(1,1);

9.KMP

#include<bits/stdc++.h>
using namespace std; int next[20]; //优化过后的next 数组求法
void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k]) { ++j; ++k; //较之前next数组求法，改动在下面4行
            if (p[j] != p[k]) next[j] = k;   //之前只有这一行
            else
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
                next[j] = next[k]; } else { k = next[k]; } } } //pos穿入的不是下标！！是真正的数字位置
int KmpSearch(char* s, char* p,int pos) { int i = pos-1; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] //next[j]即为j所对应的next值
            j = next[j]; } } if (j == pLen) return i - j; else
        return -1; } int main() { int m; char S[20]="abcdfadabddfa"; char T[20]="df"; GetNextval(T,next); m=KmpSearch(S,T,1);//第一个位置开始找起
    printf("%d",m); return 0; }

10拓展欧几里得

 

//已知a,b,c，求ax+by=c的一组特解
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll g=exgcd(b,a%b,x,y),t;
    t=x;
    x=y;
    y=t-(a/b)*y;
    return g;//g是全程不变的，就是a,b的最大公约数。
}
int main()
{
    ll a,b,c,x,y;
    cin>>a>>b>>c;
    ll g=exgcd(a,b,x,y);
    if(c%g==0)
    {
        printf("%lld %lld\n",x*c/g,y*c/g);//这是特解
        //通解为 x=x0+b/g*t  y=y0-a/g*t  t为任意整数
    }
    else
        puts("-1");
}

 

 

 

11.欧拉函数

 

对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.

 

   φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

 

//直接求解欧拉函数
int euler(int n)  //返回euler(n)
{
    int res=n,a=n;
    for(int i=2; i*i<=a; i++)
    {
        if(a%i==0)
        {
            res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
            while(a%i==0)
                a/=i;
        }
    }
    if(a>1)
        res=res/a*(a-1);
    return res;
}

12.快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b,q,mod;
//口诀：while指数，指数与一乘底数，底数平方，指数右移
inline ll qmul(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1ll)
    ans=(ans*base)%mod;
     base=(base*base)%mod;
        b>>=1ll;
    }
    return ans;
}

int main()
{
    cin>>b>>q>>mod;
    ll x=qmul(b,q);
    printf("%lld^%lld mod %lld=%lld",b,q,mod,x);
    return 0;
}

13.二进制

long long k, n, ans;
stack<int> S;

int main() {
    cin >> k >> n;
    while(n) S.push(n & 1), n >>= 1;
  //再反转一下
    cout << ans << endl;
    return 0;
}

//或者
  while(k)a[++l]=k%2,k/=2;//先转二进制

14.__int128

#include <bits/stdc++.h>
using namespace std;

void scan(__int128 &x)//输入
{
    x = 0;
    int f = 1;
    char ch;
    if((ch = getchar()) == '-') f = -f;
    else x = x*10 + ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        x = x*10 + ch-'0';
    x *= f;
}

void print(__int128 x)//输出
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
     if(x > 9) _print(x/10);
    putchar(x%10 + '0');
}

int main()
{
    __int128 a, b;
    scan(a); scan(b);
    print(a + b);
    return 0;
}

15.fill,memset

大空间用fill!!!
fill(&a[0][0],&a[99][99],inf);
偷懒的话,memset(a,127,sizeof(a))
但是取不到int类型最大值
01111111 01111111 01111111 01111111 差了点的
memset是按字节填充的！！！
一个字节=8位
位是最小的单位
int是4个字节 
所以int化为位的话是这样
————|————3f
————|————ff
————|————ff
————|————ff
0x3fffffff这么看的 ！(这是int类型最大值了）
f（15）是16进制来算的 int类型最大值
01111111 11111111 11111111 11111111
    memset(a[1],-1,sizeof(a[1]));
fill(&a[4][0],&a[4][6],-1);
这么写是填充这一行！！！
试用于滚动数组

16.玄学加速

#define ri register int
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
char BB[1 << 18], *S = BB, *T = BB;
inline int read(){
    int x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
inline int min(int a, int b)
{
    int c = (a - b) >> 31;
    return a & c | b & ~c;
}

inline int max(int a, int b)
{
    int c = (a - b) >> 31;
    return b & c | a & ~c;
}

17.ST表

https://www.luogu.org/problemnew/show/P3865

ST表学习 作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例 举例： 给出一数组A[0~5] = {5,4,6,10,1,12},则区间[2,5]之间的最值为1。 方法：ST算法分成两部分：离线预处理 （nlogn）和 在线查询（O(1)）。虽然还可以使用线段树、树状链表等求解区间最值，但是ST算法要比它们更快，而且适用于在线查询。 （1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。 （2）在线查询：对给定区间进行分割，借助该二维数组求最值 具体解释： （1）离线预处理： ST算法使用DP思想求解区间最值，貌似属于区间动态规划，不过区间在增加时，每次并不是增加一个长度，而是使用倍增的思想，每次增加2^i个长度。 使用F[i,j]表示以i为起点，区间长度为2^j的区间最值，此时区间为[i,i + 2^j - 1]。 比如，F[0,2]表示区间[0,3]的最小值，即等于4，F[2,2]表示区间[2,5]的最小值，即等于1。 在求解F[i,j]时，ST算法是先对长度为2^j的区间[i,i + 2^j - 1]分成两等份，每份长度均为2^(j - 1)。之后在分别求解这两个区间的最值F[i,j - 1]和F[i + 2^(j - 1),j - 1]。，最后在结合这两个区间的最值，求出整个区间的最值。特殊情况，当j = 0时，区间长度等于1，即区间中只有一个元素，此时F[i,0]应等于每一个元素的值。 举例：要求解F[1,2]的值，即求解区间[1,4] = {4,6,10,1}的最小值，此时需要把这个区间分成两个等长的区间，即为[1,2]和[3,4]，之后分别求解这两个区间的最小值。此时这两个区间最小值分别对应着F[1,1] 和 F[3,1]的值。 状态转移方程是 F[i,j] = min(F[i,j - 1],F[i + 2^(j - 1),j - 1]) 初始状态为：F[i,0] = A[i]。 在根据状态转移方程递推时，是对每一元素，先求区间长度为1的区间最值，之后再求区间长度为2的区间最值，之后再求区间长度为4的区间最值….，最后，对每一个元素，在求解区间长度为log2^n的区间最值后，算法结束，其中n表示元素个数。 即：先求F[0][1]，F[1][1]，F[2][1]，F[3][1]，,，F[n][1]，再求.F[0][2]，F[1][2]，F[2][2]，F[3][2]，,，F[m][2]，… 。 （2）在线处理：这里我们是已知待查询的区间[x,y]，求解其最值。 在预处理期间，每一个状态对应的区间长度都为2^i。由于给出的待查询区间长度不一定恰好为2^i，因此我们应对待查询的区间进行处理。 这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：（1）这两个小区间要能覆盖整个区间（2）为了利用预处理的结果，要求小区间长度相等且都为2^i。注意两个小区间可能重叠。 如：待查询的区间为[3,11]，先尽量等分两个区间，则先设置为[3,7]和[8,11]。之后再扩大这两个区间，让其长度都等于为2^i。刚划分的两个区间长度分别为5和4，之后继续增加区间长度，直到其成为2^i。此时满足两个条件的最小区间长度为8,此时i = 3。 在程序计算求解区间长度时，并没有那么麻烦，我们可以直接得到i，即等于直接对区间长度取以2为底的对数。这里，对于区间[3,11]，其分解的区间长度为int（log(11 - 3 + 1)） = 3，这里log是以2为底的。 根据上述思想，可以把待查询区间[x，y]分成两个小区间[x，x + 2^i - 1] 和 [y - 2^i + 1，y] ，其又分别对应着F[x,i]和F[y - 2^i + 1,i]，此时为了求解整个区间的最小值，我们只需求这两个值得最小值即可，此时复杂度是O(1)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=30005;
#define inf 0x3f3f3f3f
typedef long long ll;

int stmax[maxn][20],stmin[maxn][20],mn[maxn];
int a[maxn];
int t,q,n;
int x,y;

void init()
{
    mn[0]=-1;
    for(int i=1; i<=n; i++)
    {
        //是否为2^n
        mn[i]=((i&(i-1)==0))?mn[i-1]+1:mn[i-1];
        stmax[i][0]=stmin[i][0]=a[i];
    }
    for(int j=1; j<=mn[n]; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
        {
            stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
            stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
        }
}

int rmq_max(int L,int R)
{
    int k=mn[R-L+1];
    return max(stmax[L][k],stmax[R-(1<<k)+1][k]);
}

int rmq_min(int L,int R)
{
    int k=mn[R-L+1];
    return min(stmin[L][k],stmin[R-(1<<k)+1][k]);
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        init();
        cin>>q;
        while(q--)
        {
            cin>>x>>y;
            cout<<rmq_max(x,y)<<" "<<rmq_min(x,y)<<endl;
        }
    }
    return 0;
}

 18.gcd

gcd(f(m),f(n))=f(gcd(m,n))

19.burnset,polyapolya定理

http://blog.csdn.net/liangzhaoyang1/article/details/72639208

20.负环

https://www.luogu.org/problemnew/show/P3385

 

21.manacher算法

https://www.luogu.org/problemnew/show/P3805 

 

22.Link Cut Tree （动态树）

https://www.luogu.org/problemnew/show/P3690

 

23.割点（割顶）

 https://www.luogu.org/problemnew/show/P3388

 

24.LCA(最近公共父节点）

http://www.cnblogs.com/planche/p/8904570.html

int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void uone(int a,int b)
{
    int t1=find(a),t2=find(b);
    if(t1!=t2)
    {
        if(rk[t1]>rk[t2])fa[t2]=t1;
        else fa[t1]=t2;
        if(rk[t1]==rk[t2])rk[t2]++;
    }
}
void LCA(int u)
{
    acr[u]=u;
    ins[u]=1;
    for(int p=fst[u]; p; p=e[p].nxt)
    {
        int v=e[p].to;
        if(ins[v])continue;
        LCA(v);
        uone(u,v);
        acr[find(u)]=u;
    }
    for(int p=fst_[u]; p; p=e_[p].nxt)
    {
        int v=e_[p].to;
        if(ins[v])ans[e_[p].idx]=acr[find(v)];
    }
}

 

25.二进制快速转换（补零）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c)
{
    return min(min(a, b), c);
}
template <class T> inline T max(T a, T b, T c)
{
    return max(max(a, b), c);
}
template <class T> inline T min(T a, T b, T c, T d)
{
    return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d)
{
    return max(max(a, b), max(c, d));
}
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define mp make_pair
#define pb push_back
const int maxn = 100005;
#define mod 9999973
const int N=10005;
// name*******************************
int n,k;
int f[20][N];
    int ans=0;
    int s[N];
    int tot=0;
// function******************************
void dfs(int x,int cnt,int p){
if(x>n){
s[++tot]=p;
return;
}
dfs(x+1,cnt,p);
if(!((p>>(x-1))&1))
dfs(x+1,cnt+1,p|(1<<x));
}

//***************************************
int main()
{
//    freopen("test.txt", "r", stdin);
n=3;
dfs(0,0,0);
cout.fill('0');
For(i,1,tot){
    char binary[255];
itoa(s[i], binary, 2);
cout<<setw(4)<<binary<<endl;
}
    return 0;
}

 

26.高斯消元

https://www.luogu.org/problemnew/show/P3389

 记得fabs！！！

#include<bits/stdc++.h>
typedef long long ll;
const int inf=0x3f3f3f3f;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define FFor(i,a,b) for(int i=a;i>=b;i--)
template <class T> inline T min(T a,T b,T c)
{
    return min(min(a,b),c);
}
template <class T> inline T max(T a,T b,T c)
{
    return max(max(a,b),c);
}
template <class T> inline T min(T a,T b,T c,T d)
{
    return min(min(a,b),min(c,d));
}
template <class T> inline T max(T a,T b,T c,T d)
{
    return max(max(a,b),max(c,d));
}
using namespace std;
const int N=1e4;
const double eps=1e-7;
//***********name**************
double matrix[N][N];
double ans[N];
int n;
//***********function**********
inline int gauss()
{
    For(i,1,n)
    {
        int t=i;
        For(j,i+1,n)
        if(fabs(matrix[j][i])>fabs(matrix[t][i]))
            t=j;
        if(t!=i)
            For(j,i,n+1)
            swap(matrix[i][j],matrix[t][j]);
        For(j,i+1,n)
        {
            double x=matrix[j][i]/matrix[i][i];
            For(k,i,n+1)
            matrix[j][k]-=x*matrix[i][k];
        }
    }
    FFor(i,n,1)
    {
        if(matrix[i][i]<eps)return false;
        ans[i]=matrix[i][n+1];
        For(j,i+1,n)
        ans[i]-=matrix[i][j]*ans[j];
        ans[i]/=matrix[i][i];
    }
    return true;
}

//******************************
int main()
{
//    freopen("test.txt","r",stdin);
    cin>>n;
    For(i,1,n)
    For(j,1,n+1)
    cin>>matrix[i][j];
    if(gauss())
    {
        For(i,1,n)
        printf("%.2f\n",ans[i]);
    }
    else
    {
        cout<<"No Solution";
    }
    return 0;
}

 

void gauss()
{
    For(i,1,n)
    {
        int t=i;
        For(j,i+1,n)
        if(matrix[j][i])
        {
            t=j;
            break;
        }
        if(t!=i)
            For(j,1,n+1)
            swap(matrix[t][j],matrix[i][j]);
        For(j,i+1,n)
        {
            if(matrix[j][i])
                For(k,1,n+1)
                matrix[j][k]^=matrix[i][k];
        }
    }
}

 

 

26.逆元

 

https://www.luogu.org/problemnew/show/P3811 

 

https://www.cnblogs.com/linyujun/p/5194184.html

(a  /  b) % p = (a * inv(b) ) % p = (a % p * inv(b) % p) % p

1.费马小定理（p为质数）

inv(a) = a^(p-2) (mod p)  (快速幂）

2.扩展欧几里德

#include<cstdio>
typedef long long LL;
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
    if (!b) {d = a, x = 1, y = 0;}
    else{
        ex_gcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}
LL inv(LL t, LL p){//如果不存在，返回-1 
    LL d, x, y;
    ex_gcd(t, p, x, y, d);
    return d == 1 ? (x % p + p) % p : -1;
}
int main(){
    LL a, p;
    while(~scanf("%lld%lld", &a, &p)){
        printf("%lld\n", inv(a, p));
    }
}