# ZJUT4板子
## 基础

vector, 变长数组，倍增的思想
  size()  返回元素个数
  empty()  返回是否为空
  clear()  清空
  front()/back()返回第一个/最后一个数
  push_back()插入一个元素
  pop_back()删除最后一个元素
  begin()/end()
  []
  支持比较运算<>=，按字典序

pair<int, int>存储一个二元组
  first, 第一个元素
  second, 第二个元素
  支持比较运算，以first为第一关键字；
  以second为第二关键字（字典序）

string，字符串
  size()/length()  返回字符串长度
  empty()
  clear()
  substr(起始下标，(子串长度))  返回子串
  c_str()  返回字符串所在字符数组的起始地址

queue, 队列
  size()
  empty()
  push()  向队尾插入一个元素
  front()  返回队头元素
  back()  返回队尾元素
  pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
  size()
  empty()
  push()  插入一个元素
  top()  返回堆顶元素
  pop()  弹出堆顶元素
 定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
  size()
  empty()
  push()  向栈顶插入一个元素
  top()  返回栈顶元素
  pop()  弹出栈顶元素

deque, 双端队列
  size()
  empty()
  clear()
  front()/back()
  push_back()/pop_back()
  push_front()/pop_front()
  begin()/end()
  []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
  size()
  empty()
  clear()
  begin()/end()
  ++, -- 返回前驱和后继，时间复杂度 O(logn)

set/multiset
  基于平衡二叉树（红黑树），动态维护有序数列
  insert()  插入一个数
  find()  查找一个数
  count()  返回某一个数的个数
  erase()
  (1) 输入是一个数x，删除所有x
  O(k + logn)
  (2) 输入一个迭代器，删除这个迭代器

lower_bound() && upper_bound()
lower_bound(x)
返回大于等于x的最小的数的迭代器
upper_bound(x)
返回大于x的最小的数的迭代器

map/multimap
  基于平衡二叉树（红黑树），动态维护有序数列
  insert()  插入的数是一个pair
  erase()  输入的参数是pair或者迭代器
  find()
  []  注意multimap不支持此操作。
  时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
 和上面类似，增删改查的时间复杂度是 O(1)
 不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 压位
        bitset<10000> s;
          ~, &, |, ^
          >>, <<
          ==, !=
          []

  count()  返回有多少个1

  any()  判断是否至少有一个1
  none()  判断是否全为0

  set()  把所有位置成1
  set(k, v)  将第k位变成v
  reset()  把所有位变成0
  flip()  等价于~
  flip(k) 把第k位取反

### mutiset简单记录：

struct cmp{
    bool operator()(const ...&a,const ...&b){
        return ....;
    }
};
set<Elem,cmp>c;
c.size();//返回大小
c.empty();//返回是否为空
count(elem);//返回elem元素的个数
find(elem);//返回元素值为elem的第一个元素，如果没有返回end()
lower_bound(elem);
upper_bound (elem);
c.begin();
c.end();
c.insert(elem);
distance(..,..)//返回两者之间的距离
c.erase(elem)//删除与elem相等的所有元素，返回被移除的元素个数。
c.erase(pos)//移除迭代器pos所指位置元素，无返回值。
c.clear()//移除所有元素，将容器清空

### bitset相关

///C++的 bitset 在 bitset 头文件中，
///它是一种类似数组的结构.
/// 它的每一个元素只能是０或１.
/// 每个元素仅用１bit空间。


///常用构造
//用字符串构造时，字符串只能包含 '0' 或 '1' ，否则会抛出异常。
//
//构造时，需在<>中表明bitset 的大小(即size)。
//
//在进行有参构造时，若参数的二进制表示比bitset的size小，则在前面用０补充(如上面的栗子)；若比bitsize大，参数为整数时取后面部分，参数为字符串时取前面部分(如下面栗子)：
bitset<4> bitset1;
//无参构造，长度为４，默认每一位为０

bitset<8> bitset2(12);
//长度为８，二进制保存，前面用０补充

string s = "100101";
bitset<10> bitset3(s);
//长度为10，前面用０补充

char s2[] = "10101";
bitset<13> bitset4(s2);
//长度为13，前面用０补充


///可用操作符
bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));

cout << (foo^=bar) << endl;       // 1010 (foo对bar按位异或后赋值给foo)
cout << (foo&=bar) << endl;       // 0010 (按位与后赋值给foo)
cout << (foo|=bar) << endl;       // 0011 (按位或后赋值给foo)

cout << (foo<<=2) << endl;        // 1100 (左移２位，低位补０，有自身赋值)
cout << (foo>>=1) << endl;        // 0110 (右移１位，高位补０，有自身赋值)

cout << (~bar) << endl;           // 1100 (按位取反)
cout << (bar<<1) << endl;         // 0110 (左移，不赋值)
cout << (bar>>1) << endl;         // 0001 (右移，不赋值)

cout << (foo==bar) << endl;       // false (0110==0011为false)
cout << (foo!=bar) << endl;       // true  (0110!=0011为true)

cout << (foo&bar) << endl;        // 0010 (按位与，不赋值)
cout << (foo|bar) << endl;        // 0111 (按位或，不赋值)
cout << (foo^bar) << endl;        // 0101 (按位异或，不赋值)


///可用函数
bitset<8> foo ("10011011");

cout << foo.count() << endl;
//5　　（count函数用来求bitset中1的位数，foo中共有５个１
cout << foo.size() << endl;
//8　　（size函数用来求bitset的大小，一共有８位
cout << foo.test(0) << endl;
//true　　（test函数用来查下标处的元素是０还是１，并返回false或true，此处foo[0]为１，返回true
//test访问比[]安全，因为会检查下标越界
cout << foo.test(2) << endl;
//false　　（同理，foo[2]为０，返回false
cout << foo.any() << endl;
//true　　（any函数检查bitset中是否有１
cout << foo.none() << endl;
//false　　（none函数检查bitset中是否没有１
cout << foo.all() << endl;
//false　　（all函数检查bitset中是全部为１

///可用函数2
bitset<8> foo ("10011011");

cout << foo.flip(2) << endl;
//10011111　　（flip函数传参数时，用于将参数位取反，本行代码将foo下标２处"反转"，即０变１，１变０
cout << foo.flip() << endl;
//01100000　　（flip函数不指定参数时，将bitset每一位全部取反

cout << foo.set() << endl;
//11111111　　（set函数不指定参数时，将bitset的每一位全部置为１
cout << foo.set(3,0) << endl;
//11110111　　（set函数指定两位参数时，将第一参数位的元素置为第二参数的值，本行对foo的操作相当于foo[3]=0
cout << foo.set(3) << endl;
//11111111　　（set函数只有一个参数时，将参数下标处置为１

cout << foo.reset(4) << endl;
//11101111　　（reset函数传一个参数时将参数下标处置为０
cout << foo.reset() << endl;
//00000000　　（reset函数不传参数时将bitset的每一位全部置为０


///类型转换
bitset<8> foo ("10011011");

string s = foo.to_string();
//将bitset转换成string类型
unsigned long a = foo.to_ulong();
//将bitset转换成unsigned long类型
unsigned long long b = foo.to_ullong();
//将bitset转换成unsigned long long类型

cout << s << endl;
//10011011
cout << a << endl;
//155
cout << b << endl;
//155

### 二分相关

///整数二分板子
bool check(int x) {/* ... */}

// 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
            //mid满足条件，那么
        else
            l = mid + 1;
    }
    return l;
}

// check()判断mid是否满足性质
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
            //mid满足条件，边界在mid后面包括mid
        else
            r = mid - 1;
        //mid不满足条件，边界在mid前面
    }
    return l;
}

///浮点数二分
bool check(double x) {/* ... */}
// 检查x是否满足某种性质

double bsearch_3(double l, double r) {
    const double eps = 1e-6;
    // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

///lower_bound( begin,end,num)：
// 从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，
// 找到返回该数字的地址，不存在则返回end。
// 通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

///upper_bound( begin,end,num)：
// 从数组的begin位置到end-1位置二分查找第一个大于num的数字，
// 找到返回该数字的地址，不存在则返回end。
// 通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

///在从大到小的排序数组中，重载lower_bound()和upper_bound()
///lower_bound( begin,end,num,greater<type>() ):
//从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字


///upper_bound( begin,end,num,greater<type>() ):
// 从数组的begin位置到end-1位置二分查找第一个小于num的数字

## 搜索
### A*

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 5010;
const int maxm = 400010;
const double inf = 2e9;
int n, m, k, u, v, cur, h[maxn], nxt[maxm], p[maxm], cnt[maxn], ans;
int cur1, h1[maxn], nxt1[maxm], p1[maxm];
double e, ww, w[maxm], f[maxn];
double w1[maxm];
bool tf[maxn];
void add_edge(int x, int y, double z) {  //正向建图函数
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
  w[cur] = z;
}
void add_edge1(int x, int y, double z) {  //反向建图函数
  cur1++;
  nxt1[cur1] = h1[x];
  h1[x] = cur1;
  p1[cur1] = y;
  w1[cur1] = z;
}
struct node {  //使用A*时所需的结构体
  int x;
  double v;
  bool operator<(node a) const { return v + f[x] > a.v + f[a.x]; }
};
priority_queue<node> q;
struct node2 {  //计算t到所有结点最短路时所需的结构体
  int x;
  double v;
  bool operator<(node2 a) const { return v > a.v; }
} x;
priority_queue<node2> Q;
int main() {
  scanf("%d%d%lf", &n, &m, &e);
  while (m--) {
    scanf("%d%d%lf", &u, &v, &ww);
    add_edge(u, v, ww);   //正向建图
    add_edge1(v, u, ww);  //反向建图
  }
  for (int i = 1; i < n; i++) f[i] = inf;
  Q.push({n, 0});
  while (!Q.empty()) {  //计算t到所有结点的最短路
    x = Q.top();
    Q.pop();
    if (tf[x.x]) continue;
    tf[x.x] = true;
    f[x.x] = x.v;
    for (int j = h1[x.x]; j; j = nxt1[j]) Q.push({p1[j], x.v + w1[j]});
  }
  k = (int)e / f[1];
  q.push({1, 0});
  while (!q.empty()) {  //使用A*算法
    node x = q.top();
    q.pop();
    cnt[x.x]++;
    if (x.x == n) {
      e -= x.v;
      if (e < 0) {
        printf("%d\n", ans);
        return 0;
      }
      ans++;
    }
    for (int j = h[x.x]; j; j = nxt[j])
      if (cnt[p[j]] <= k && x.v + w[j] <= e) q.push({p[j], x.v + w[j]});
  }
  printf("%d\n", ans);
  return 0;
}

## 图论

### Kruscal

const int maxn=1e5+5;
int n,m;
int fa[maxn];
struct side{
    int x,y,l;
}g[maxn];
bool cmp(side x,side y){
    return x.l<y.l;
}
void init(){
    for (int i=1; i<=n; i++){
        fa[i]=i;
    }
}
int find(int x){
    if (fa[x]==x) return fa[x];
    else return fa[x]=find(fa[x]);
}
int kruscal(){
    sort(g+1,g+1+m,cmp);
    int tot=0,res=0;
    for (int i=1; i<=m; i++){
        int u=find(g[i].x),v=find(g[i].y);
        if (u!=v){
            res=max(res,g[i].l);
            fa[u]=v;
            tot++;
        }
        if (tot==n-1) break;
    }
    return res;
}

### Prim

const int maxn=1e5+5;
const int INF=0X3f3f3f3f;
int n,m;
int dis[maxn];
bool flag[maxn];
int g[305][305];
struct node{
    int x,l;
    friend bool operator < (struct node a,struct node b){
        return a.l>b.l;
    }
};
int prim(){
    priority_queue<node> q;
    int res=0;
    for (int i=1; i<=n; i++) 
        dis[i]=INF;
    dis[1]=0;
    q.push({1,0});
    memset(flag,0,sizeof(flag));
    while (!q.empty()){
        node x=q.top();
        q.pop();
        int now=x.x;
        if (flag[now]==1) continue;
        flag[now]=1;
        res=max(res,dis[now]);
        for (int i=1; i<=n; i++){
            if (!flag[i] && dis[i]>g[now][i]){
                dis[i]=g[now][i];
                q.push({i,dis[i]});
            }
        }
    }
    return res;
}

### dijkstra

const int N = 2510;
const int M = 15000;
typedef pair<int, int> P;
struct DIJ{
    struct edge{
        int u, v;
        int cost;
        int next;
    }es[M];
    int head[N], pre[N];
    int d[N];
    int V, tot;
    void init(int n) {
        V = n; tot = 0;
        for (int i = 0; i <= V; i++)
            head[i] = pre[i] = -1;
    }
    void add_edge(int u, int v, int cost) {
        es[tot].u = u;
        es[tot].v = v;
        es[tot].cost = cost;
        es[tot].next = head[u];
        head[u] = tot++;
    }
    void dijkstra(int s, int d[]) {
        priority_queue<P, vector<P>, greater<P> > pq;
        for (int i = 0; i <= V; i++) d[i] = INF;
        d[s] = 0;
        pq.push(P(0, s));

        while (pq.size()) {
            P p = pq.top(); pq.pop();
            int v = p.second;
            if (d[v] < p.first) continue;
            for (int i = head[v]; i != -1; i = es[i].next) {
                int from = es[i].u;
                int to = es[i].v;
                int cost = es[i].cost;
                if (d[to] > d[from] + cost) {
                    d[to] = d[from] + cost;
                    pq.push(P(d[to], to));
                    pre[to] = from;
                }
            }
        }
    }
    vector<int> get_path(int t) {
        vector<int> path;
        for (; t != -1; t = pre[t]) path.push_back(t);
        reverse(path.begin(), path.end());
        return path;
    }
}G;

### bellman判负环

bool Bellman_Ford() {
  for (int i = 0; i < n; i++) {
    bool jud = false;
    for (int j = 1; j <= n; j++)
      for (int k = h[j]; ~k; k = nxt[k])
        if (dist[j] > dist[p[k]] + w[k])
          dist[j] = dist[p[k]] + w[k], jud = true;
    if (!jud) break;
  }
  for (int i = 1; i <= n; i++)
    for (int j = h[i]; ~j; j = nxt[j])
      if (dist[i] > dist[p[j]] + w[j]) return false;
  return true;
}

### K短路

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 200010;
int n, m, s, t, k, x, y, ww, cnt, fa[maxn];
struct Edge {
  int cur, h[maxn], nxt[maxn], p[maxn], w[maxn];
  void add_edge(int x, int y, int z) {
    cur++;
    nxt[cur] = h[x];
    h[x] = cur;
    p[cur] = y;
    w[cur] = z;
  }
} e1, e2;
int dist[maxn];
bool tf[maxn], vis[maxn], ontree[maxn];
struct node {
  int x, v;
  node* operator=(node a) {
    x = a.x;
    v = a.v;
    return this;
  }
  bool operator<(node a) const { return v > a.v; }
} a;
priority_queue<node> Q;
void dfs(int x) {
  vis[x] = true;
  for (int j = e2.h[x]; j; j = e2.nxt[j])
    if (!vis[e2.p[j]])
      if (dist[e2.p[j]] == dist[x] + e2.w[j])
        fa[e2.p[j]] = x, ontree[j] = true, dfs(e2.p[j]);
}
struct LeftistTree {
  int cnt, rt[maxn], lc[maxn * 20], rc[maxn * 20], dist[maxn * 20];
  node v[maxn * 20];
  LeftistTree() { dist[0] = -1; }
  int newnode(node w) {
    cnt++;
    v[cnt] = w;
    return cnt;
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (v[x] < v[y]) swap(x, y);
    int p = ++cnt;
    lc[p] = lc[x];
    v[p] = v[x];
    rc[p] = merge(rc[x], y);
    if (dist[lc[p]] < dist[rc[p]]) swap(lc[p], rc[p]);
    dist[p] = dist[rc[p]] + 1;
    return p;
  }
} st;
void dfs2(int x) {
  vis[x] = true;
  if (fa[x]) st.rt[x] = st.merge(st.rt[x], st.rt[fa[x]]);
  for (int j = e2.h[x]; j; j = e2.nxt[j])
    if (fa[e2.p[j]] == x && !vis[e2.p[j]]) dfs2(e2.p[j]);
}
int main() {
  scanf("%d%d%d%d%d", &n, &m, &s, &t, &k);
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d", &x, &y, &ww), e1.add_edge(x, y, ww), e2.add_edge(y, x, ww);
  Q.push({t, 0});
  while (!Q.empty()) {
    a = Q.top();
    Q.pop();
    if (tf[a.x]) continue;
    tf[a.x] = true;
    dist[a.x] = a.v;
    for (int j = e2.h[a.x]; j; j = e2.nxt[j]) Q.push({e2.p[j], a.v + e2.w[j]});
  }
  if (k == 1) {
    if (tf[s])
      printf("%d\n", dist[s]);
    else
      printf("-1\n");
    return 0;
  }
  dfs(t);
  for (int i = 1; i <= n; i++)
    if (tf[i])
      for (int j = e1.h[i]; j; j = e1.nxt[j])
        if (!ontree[j])
          if (tf[e1.p[j]])
            st.rt[i] = st.merge(
                st.rt[i],
                st.newnode({e1.p[j], dist[e1.p[j]] + e1.w[j] - dist[i]}));
  for (int i = 1; i <= n; i++) vis[i] = false;
  dfs2(t);
  if (st.rt[s]) Q.push({st.rt[s], dist[s] + st.v[st.rt[s]].v});
  while (!Q.empty()) {
    a = Q.top();
    Q.pop();
    cnt++;
    if (cnt == k - 1) {
      printf("%d\n", a.v);
      return 0;
    }
    if (st.lc[a.x])
      Q.push({st.lc[a.x], a.v - st.v[a.x].v + st.v[st.lc[a.x]].v});
    if (st.rc[a.x])
      Q.push({st.rc[a.x], a.v - st.v[a.x].v + st.v[st.rc[a.x]].v});
    x = st.rt[st.v[a.x].x];
    if (x) Q.push({x, a.v + st.v[x].v});
  }
  printf("-1\n");
  return 0;
}

### 点分治

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,M=1e7+6;
int n, m, u, v, w,Q[N],ans[N];
int root,cnt,S,temp[N],dis[N],max_childrenpart[N],size[N];
bool use[N],judge[M];
// judge i 与当前根距离为i的路径是否存在
// use 表示该点有没有被遍历过
struct node
{
    int link, w;
};
vector <node> f[N];
queue <int> q;
void find_root(int x,int fa)// 板子
{
    max_childrenpart[x] = 0;
    size[x] = 1;
    for(auto i:f[x])
    {
        if(i.link==fa||use[i.link])
            continue;
        find_root(i.link, x);
        size[x] += size[i.link];
        max_childrenpart[x] = max(size[i.link],max_childrenpart[x]);
    }
    max_childrenpart[x] = max(max_childrenpart[x],S-max_childrenpart[x]);
    if(max_childrenpart[x]<max_childrenpart[root])
        root = x;
}
void get_dis(int x,int fa) //板子
{
    temp[++cnt] = dis[x];
    for(auto i:f[x])
    {
        if(use[i.link]||i.link==fa)
            continue;
        dis[i.link] = dis[x] + i.w;
        get_dis(i.link, x);
    }
}
void solve(int root)//不同题不同
{
    while(!q.empty())
        q.pop();
    for(auto i:f[root])
    {
        if(use[i.link])
            continue;
        cnt = 0; // 所有点距离的计数器
        dis[i.link] = i.w; // 第一次要初始化一下
        get_dis(i.link,root);//计算距离root节点的距离
        for (int j = 1; j <= cnt; j++)
        {
            for (int k = 1; k <= m;k++)//这里肯定是可以优化的 因为没优化re了（judge爆了
            {
                if(Q[k]>=temp[j])//询问路径大于 遍历的节点到根的距离说明可能存在
                {
                    if(judge[Q[k]-temp[j]])
                    {
                        // 如果非当前子树存在到根距离为Q[k]-dis[j]的点
                        // 说明答案存在
                        ans[k] = 1;
                    }
                }
            }
        }
        for (int j = 1; j <= cnt;j++)
        {
            q.push(temp[j]);
            judge[temp[j]] = 1;
        }
    }
    while(!q.empty())                    
    {
        judge[q.front()] = 0;// 撤回
        q.pop();
    }
}
void divided(int x)//板子
{
    use[x] = 1;
    judge[0] = 1;
    solve(x);
    for(auto i:f[x])
    {
        if(use[i.link])
            continue;
        // 初始化根节点
        root = 0;
        max_childrenpart=n+1;
        //反正一定要大不然可能不会更新，之前max_childrenpart=size[i.link]是错的
        S= size[i.link];
        find_root(i.link,0);
        divided(root);
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i < n;i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        f[u].emplace_back((node){v, w});
        f[v].emplace_back((node){u, w});
    }
    for (int i = 1; i <= m;i++)
        scanf("%d", &Q[i]);
    root = 0;
    S=max_childrenpart[root] = n;
    find_root(1,0);//先找到重心
    divided(root);//重心开始第一次分治
    for (int i = 1; i <= m;i++)
    {
        if(ans[i])
            printf("AYE\n");
        else
            printf("NAY\n");
    }
    return 0;
}

### 树上启发合并

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

const int N = 2e5 + 5;

int n;

// g[u]: 存储与 u 相邻的结点
vector<int> g[N];

// sz: 子树大小
// big: 重儿子
// col: 结点颜色
// L[u]: 结点 u 的 DFS 序
// R[u]: 结点 u 子树中结点的 DFS 序的最大值
// Node[i]: DFS 序为 i 的结点
// ans: 存答案
// cnt[i]: 颜色为 i 的结点个数
// totColor: 目前出现过的颜色个数
int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn;
int ans[N], cnt[N], totColor;

void add(int u) {
  if (cnt[col[u]] == 0) ++totColor;
  cnt[col[u]]++;
}
void del(int u) {
  cnt[col[u]]--;
  if (cnt[col[u]] == 0) --totColor;
}
int getAns() { return totColor; }

void dfs0(int u, int p) {
  L[u] = ++totdfn;
  Node[totdfn] = u;
  sz[u] = 1;
  for (int v : g[u])
    if (v != p) {
      dfs0(v, u);
      sz[u] += sz[v];
      if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
  R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {
  // 计算轻儿子的答案
  for (int v : g[u])
    if (v != p && v != big[u]) {
      dfs1(v, u, false);
    }
  // 计算重儿子答案并保留计算过程中的数据（用于继承）
  if (big[u]) {
    dfs1(big[u], u, true);
  }
  for (int v : g[u])
    if (v != p && v != big[u]) {
      // 子树结点的 DFS 序构成一段连续区间，可以直接遍历
      for (int i = L[v]; i <= R[v]; i++) {
        add(Node[i]);
      }
    }
  add(u);
  ans[u] = getAns();
  if (keep == false) {
    for (int i = L[u]; i <= R[u]; i++) {
      del(Node[i]);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs0(1, 0);
  dfs1(1, 0, false);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}

### 虚树

inline bool cmp(const int x, const int y) { return id[x] < id[y]; }

void build() {
  sort(h + 1, h + k + 1, cmp);
  sta[top = 1] = 1, g.sz = 0, g.head[1] = -1;
  // 1 号节点入栈，清空 1 号节点对应的邻接表，设置邻接表边数为 1
  for (int i = 1, l; i <= k; ++i)
    if (h[i] != 1) {
      //如果 1 号节点是关键节点就不要重复添加
      l = lca(h[i], sta[top]);
      //计算当前节点与栈顶节点的 LCA
      if (l != sta[top]) {
        //如果 LCA 和栈顶元素不同，则说明当前节点不再当前栈所存的链上
        while (id[l] < id[sta[top - 1]])
          //当次大节点的 Dfs 序大于 LCA 的 Dfs 序
          g.push(sta[top - 1], sta[top]), top--;
        //把与当前节点所在的链不重合的链连接掉并且弹出
        if (id[l] > id[sta[top - 1]])
          //如果 LCA 不等于次大节点（这里的大于其实和不等于没有区别）
          g.head[l] = -1, g.push(l, sta[top]), sta[top] = l;
        //说明 LCA 是第一次入栈，清空其邻接表，连边后弹出栈顶元素，并将 LCA 入栈
        else
          g.push(l, sta[top--]);
        //说明 LCA 就是次大节点，直接弹出栈顶元素
      }
      g.head[h[i]] = -1, sta[++top] = h[i];
      //当前节点必然是第一次入栈，清空邻接表并入栈
    }
  for (int i = 1; i < top; ++i)
    g.push(sta[i], sta[i + 1]);  //剩余的最后一条链连接一下
  return;
}

### 二分图
#### 匈牙利算法

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

### 割点

#include <bits/stdc++.h>
using namespace std;
int n, m;  // n：点数 m：边数
int num[100001], low[100001], inde, res;
// num：记录每个点的时间戳
// low：能不经过父亲到达最小的编号，inde：时间戳，res：答案数量
bool vis[100001], flag[100001];  // flag: 答案 vis：标记是否重复
vector<int> edge[100001];        // 存图用的
void Tarjan(int u, int father) {  // u 当前点的编号，father 自己爸爸的编号
  vis[u] = true;                  // 标记
  low[u] = num[u] = ++inde;  // 打上时间戳
  int child = 0;             // 每一个点儿子数量
  for (auto v : edge[u]) {   // 访问这个点的所有邻居 （C++11）

    if (!vis[v]) {
      child++;                       // 多了一个儿子
      Tarjan(v, u);                  // 继续
      low[u] = min(low[u], low[v]);  // 更新能到的最小节点编号
      if (father != u && low[v] >= num[u] &&
          !flag
              [u])  // 主要代码
                    // 如果不是自己，且不通过父亲返回的最小点符合割点的要求，并且没有被标记过
                    // 要求即为：删了父亲连不上去了，即为最多连到父亲
      {
        flag[u] = true;
        res++;  // 记录答案
      }
    } else if (v != father)
      low[u] =
          min(low[u], num[v]);  // 如果这个点不是自己，更新能到的最小节点编号
  }
  if (father == u && child >= 2 &&
      !flag[u]) {  // 主要代码，自己的话需要 2 个儿子才可以
    flag[u] = true;
    res++;  // 记录答案
  }
}
int main() {
  cin >> n >> m;                  // 读入数据
  for (int i = 1; i <= m; i++) {  // 注意点是从 1 开始的
    int x, y;
    cin >> x >> y;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }                             // 使用 vector 存图
  for (int i = 1; i <= n; i++)  // 因为 Tarjan 图不一定连通
    if (!vis[i]) {
      inde = 0;      // 时间戳初始为 0
      Tarjan(i, i);  // 从第 i 个点开始，父亲为自己
    }
  cout << res << endl;
  for (int i = 1; i <= n; i++)
    if (flag[i]) cout << i << " ";  // 输出结果
  return 0;
}

### 割边

int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  father[u] = fa;
  low[u] = dfn[u] = ++dfs_clock;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else if (dfn[v] < dfn[u] && v != fa) {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

### tarjan

int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 scc 的编号
int sz[N];       // 强连通 i 的大小
void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

## 网络流
### 最大流

#### Dinic

#define maxn 250
#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  int d[maxn], cur[maxn];
  bool vis[maxn];

  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  int DFS(int x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f;
    for (int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i] ^ 1].flow -= f;
        flow += f;
        a -= f;
        if (a == 0) break;
      }
    }
    return flow;
  }

  int Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    while (BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, INF);
    }
    return flow;
  }
};

#### ISAP

struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

bool operator<(const Edge& a, const Edge& b) {
  return a.from < b.from || (a.from == b.from && a.to < b.to);
}

struct ISAP {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool vis[maxn];
  int d[maxn];
  int cur[maxn];
  int p[maxn];
  int num[maxn];

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t] = 1;
    d[t] = 0;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i] ^ 1];
        if (!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = 1;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
  }

  void init(int n) {
    this->n = n;
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  int Augment() {
    int x = t, a = INF;
    while (x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap - e.flow);
      x = edges[p[x]].from;
    }
    x = t;
    while (x != s) {
      edges[p[x]].flow += a;
      edges[p[x] ^ 1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
  }

  int Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    BFS();
    memset(num, 0, sizeof(num));
    for (int i = 0; i < n; i++) num[d[i]]++;
    int x = s;
    memset(cur, 0, sizeof(cur));
    while (d[s] < n) {
      if (x == t) {
        flow += Augment();
        x = s;
      }
      int ok = 0;
      for (int i = cur[x]; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (e.cap > e.flow && d[x] == d[e.to] + 1) {
          ok = 1;
          p[e.to] = G[x][i];
          cur[x] = i;
          x = e.to;
          break;
        }
      }
      if (!ok) {
        int m = n - 1;
        for (int i = 0; i < G[x].size(); i++) {
          Edge& e = edges[G[x][i]];
          if (e.cap > e.flow) m = min(m, d[e.to]);
        }
        if (--num[d[x]] == 0) break;
        num[d[x] = m + 1]++;
        cur[x] = 0;
        if (x != s) x = edges[p[x]].from;
      }
    }
    return flow;
  }
};

### 费用流

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N], ret;
bool vis[N];

void add(int u, int v, int w, int c) {
  ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }
bool spfa(int s, int t) {
  memset(dis, 0x3f, sizeof(dis));
  memcpy(cur, lnk, sizeof(lnk));
  std::queue<int> q;
  q.push(s), dis[s] = 0, vis[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (int i = lnk[u]; i; i = nxt[i]) {
      int v = ter[i];
      if (cap[i] && dis[v] > dis[u] + cost[i]) {
        dis[v] = dis[u] + cost[i];
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return dis[t] != INF;
}
int dfs(int u, int t, int flow) {
  if (u == t) return flow;
  vis[u] = 1;
  int ans = 0;
  for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
    int v = ter[i];
    if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
      int x = dfs(v, t, std::min(cap[i], flow - ans));
      if (x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
    }
  }
  vis[u] = 0;
  return ans;
}
int mcmf(int s, int t) {
  int ans = 0;
  while (spfa(s, t)) {
    int x;
    while ((x = dfs(s, t, INF))) ans += x;
  }
  return ans;
}
int main() {
  int s, t;
  scanf("%d%d%d%d", &n, &m, &s, &t);
  while (m--) {
    int u, v, w, c;
    scanf("%d%d%d%d", &u, &v, &w, &c);
    addedge(u, v, w, c);
  }
  int ans = mcmf(s, t);
  printf("%d %d\n", ans, ret);
  return 0;
}

### 上下界网络流

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300,maxm=100000;
struct edge{
  int to,next,w,num;
}lst[maxm];int len=0,first[maxn],_first[maxn];
void addedge(int a,int b,int w,int num){
  lst[len].num=num;
  lst[len].to=b;lst[len].next=first[a];lst[len].w=w;first[a]=len++;
  lst[len].num=num;
  lst[len].to=a;lst[len].next=first[b];lst[len].w=0;first[b]=len++;
}
int vis[maxn],dis[maxn],q[maxn],head,tail,s,t,T;
bool bfs(){
  vis[s]=++T;dis[s]=1;head=tail=0;q[tail++]=s;
  while(head!=tail){
    int x=q[head++];
    for(int pt=first[x];pt!=-1;pt=lst[pt].next){
      if(lst[pt].w&&vis[lst[pt].to]!=T){
    vis[lst[pt].to]=T;dis[lst[pt].to]=dis[x]+1;q[tail++]=lst[pt].to;
      }
    }
  }
  if(vis[t]==T)memcpy(_first,first,sizeof(first));
  return vis[t]==T;
}
int dfs(int x,int lim){
  if(x==t){
    return lim;
  }
  int flow=0,a;
  for(int pt=_first[x];pt!=-1;pt=lst[pt].next){
    _first[x]=pt;
    if(lst[pt].w&&dis[lst[pt].to]==dis[x]+1&&(a=dfs(lst[pt].to,min(lst[pt].w,lim-flow)))){
      lst[pt].w-=a;lst[pt^1].w+=a;flow+=a;
      if(flow==lim)return flow;
    }
  }
  return flow;
}
int dinic(){
  int ans=0,x;
  while(bfs())
    while(x=dfs(s,0x7f7f7f7f))ans+=x;
  return ans;
}
int low[maxm],ans[maxm];
int totflow[maxn],n,m;

void work(){
  memset(totflow,0,sizeof(totflow));
  memset(first,-1,sizeof(first));len=0;
  scanf("%d%d",&n,&m);
  int u,v,b;
  s=0;t=n+1;
  for(int i=1;i<=m;++i){
    scanf("%d%d%d%d",&u,&v,&low[i],&b);
    addedge(u,v,b-low[i],i);totflow[u]-=low[i];totflow[v]+=low[i];
  }
  int sum=0;
  for(int i=1;i<=n;++i){
    if(totflow[i]<0){
      addedge(i,t,-totflow[i],0);
    }else{
      sum+=totflow[i];
      addedge(s,i,totflow[i],0);
    }
  }
  if(dinic()==sum){
    puts("YES");
    for(int i=1;i<=n;++i){
      for(int pt=first[i];pt!=-1;pt=lst[pt].next){
    if(lst[pt].num==0||pt%2==0)continue;
    ans[lst[pt].num]=lst[pt].w+low[lst[pt].num];
      }
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
  }else puts("NO");
}
int main(){
  int tests;scanf("%d",&tests);
  while(tests--){
    work();if(tests)printf("\n");
  }
  return 0;
}

## 数据结构

### 关系并查集

void give (int n)
{
    for (int i=1;i<=n;i++)
    {
        father[i]=i;
        relat[i]=0; //初始关系都为0
    }
}
int find(int x)
{
    if (x==father[x]) return father[x];
    int t=find(father[x]);
    relat[x]=(relat[x]+relat[father[x]])%3; //在寻找祖先节点的过程中也要更新关系
    father[x]=t;
    return father[x];
}

### st表

void pre(){ //准备工作，初始化
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < maxn; i++){
        Logn[i] = Logn[i / 2] + 1;
    }
}

    for (int i = 1; i <= n; i++)
        f[i][0] = read();
    pre();
    for (int j = 1; j <= logn; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); // ST表具体实现
    for (int i = 1; i <= m; i++){
        int x = read(), y = read();
        int s = Logn[y - x + 1];
        printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
    }

### 树状数组

int t1[MAXN], t2[MAXN], n;

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

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}


// C++ Version
// 时间戳优化
int tag[MAXN], t[MAXN], Tag;
void reset() { ++Tag; }
void add(int k, int v) {
  while (k <= n) {
    if (tag[k] != Tag) t[k] = 0;
    t[k] += v, tag[k] = Tag;
    k += lowbit(k);
  }
}
int getsum(int k) {
  int ret = 0;
  while (k) {
    if (tag[k] == Tag) ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

//二维
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll read(){
    char c; bool op = 0;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') op = 1;
    ll res = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    return op ? -res : res;
}
const int N = 2050;
ll n, m, Q;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];
void add(ll x, ll y, ll z){
    for(int X = x; X <= n; X += X & -X)
        for(int Y = y; Y <= m; Y += Y & -Y){
            t1[X][Y] += z;
            t2[X][Y] += z * x;
            t3[X][Y] += z * y;
            t4[X][Y] += z * x * y;
        }
}
void range_add(ll xa, ll ya, ll xb, ll yb, ll z){ //(xa, ya) 到 (xb, yb) 的矩形
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}
ll ask(ll x, ll y){
    ll res = 0;
    for(int i = x; i; i -= i & -i)
        for(int j = y; j; j -= j & -j)
            res += (x + 1) * (y + 1) * t1[i][j]
                - (y + 1) * t2[i][j]
                - (x + 1) * t3[i][j]
                + t4[i][j];
    return res;
}
ll range_ask(ll xa, ll ya, ll xb, ll yb){
    return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}
int main(){
    n = read(), m = read();
    ll c;
    while(scanf("%lld",&c)!=EOF){
        if (c==1){
            ll ya = read(), xa = read(), yb = read(), xb = read(), a = read();
            range_add(xa, ya, xb, yb, a);
        }
        else {
            ll ya = read(), xa = read(), yb = read(), xb = read();
            printf("%lld\n",range_ask(xa,ya,xb,yb));
        }
    }
    return 0;
}

### 线段树（区间修改单点修改区间查询）

const int maxn=1e5+5;
struct seg_tree{
    #define p2 (p<<1)
    #define p3 ((p<<1)|1)
    ll tr[maxn<<2],lz[maxn<<2],a[maxn];
    /*  *初始化* 
        s->需维护数组 n数组长度
    */
    void init(ll *s,ll n){
        for (int i=1; i<=n; i++){
            a[i]=s[i];
        }
        build(1,n,1);
    }
    /*  *建树* 
        l->1 r->整个区间长度 p->树下标，初始赋1
    */
    void build(int l,int r,int p){
        if (l==r){
            tr[p]=a[l];
            lz[p]=0;
            return ;
        }
        int mid=l+r>>1;
        build(l,mid,p2);
        build(mid+1,r,p3);
        tr[p]=tr[p2]+tr[p3];
    }
    /*  *单点修改* 
        l->1 r->整个区间长度 k->要修改的位置 p->树下标，初始赋1 v->修改值
    */
    inline void change(int l,int r,int k,int p,ll v){
        if (l==r){
            tr[p]=v;
            lz[p]=0;
            return;
        }
        int mid=l+r>>1;
        lz[p2]+=lz[p];
        lz[p3]+=lz[p];
        lz[p]=0;
        if (k<=mid) change(l,mid,k,p2,v);
        else change(mid+1,r,k,p3,v);
        tr[p]=tr[p2]+lz[p2]*(mid-l+1)+tr[p3]+lz[p3]*(r-mid);
    }
    /*  *区间修改* 
        l->1 r->整个区间长度 le->区间修改左区间 ri->区间修改右区间 p->树下标，初始赋1 v->修改值
    */
    inline void update(int l,int r,int le,int ri,int p,ll v){
        if (l==le && r==ri){
            lz[p]+=v;
            return ;
        }
        lz[p2]+=lz[p];
        lz[p3]+=lz[p];
        lz[p]=0;
        int mid=l+r>>1;
        if (le>mid) update(mid+1,r,le,ri,p3,v);
        else if (ri<=mid) update(l,mid,le,ri,p2,v);
        else update(l,mid,le,mid,p2,v),update(mid+1,r,mid+1,ri,p3,v);
        tr[p]=tr[p2]+lz[p2]*(mid-l+1)+tr[p3]+lz[p3]*(r-mid);
    }
    /*  *区间查询* 
        l->1 r->整个区间长度 le->区间查询左区间 ri->区间查询右区间 p->树下标，初始赋1 
    */
    inline ll query(int l,int r,int le,int ri,int p){
        if (l==le && r==ri){
            return tr[p]+lz[p]*(r-l+1);
        }
        int mid=l+r>>1;
        ll ret;
        lz[p2]+=lz[p];
        lz[p3]+=lz[p];
        lz[p]=0;
        if (ri<=mid) ret=query(l,mid,le,ri,p2);
        else if(le>mid) ret=query(mid+1,r,le,ri,p3);
        else ret=query(l,mid,le,mid,p2)+query(mid+1,r,mid+1,ri,p3);
        tr[p]=tr[p2]+lz[p2]*(mid-l+1)+tr[p3]+lz[p3]*(r-mid);
        return ret;
    }
}segt;

### 区间历史最值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char nc() {
  static char buf[1000000], *p = buf, *q = buf;
  return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
             ? EOF
             : *p++;
}
inline ll rd() {  // LLONG_MIN LMAX=9,223,372,036,854,775,807
  ll s = 0, w = 1;
  char ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = nc();
  return s * w;
}
const int N = 1e5 + 7;
struct Tree {
  int mx, _mx;
  int ad, _ad;
  int st, _st;
} g[N * 4];
int a[N];
int n, m;
#define ls u * 2
#define rs u * 2 + 1
#define mid (l + r) / 2
inline void pushup(int u) {
  g[u].mx = max(g[ls].mx, g[rs].mx);
  g[u]._mx = max(g[ls]._mx, g[rs]._mx);
}
inline void pushadd(int u, int v, int _v) {
  g[u]._mx = max(g[u]._mx, g[u].mx + _v), g[u].mx += v;
  if (g[u].st == INT_MIN)
    g[u]._ad = max(g[u]._ad, g[u].ad + _v), g[u].ad += v;
  else
    g[u]._st = max(g[u]._st, g[u].st + _v), g[u].st += v;
}
inline void pushset(int u, int v, int _v) {
  g[u]._mx = max(g[u]._mx, _v), g[u].mx = v;
  g[u]._st = max(g[u]._st, _v), g[u].st = v;
}
inline void pushdown(int u, int l, int r) {
  if (g[u].ad)
    pushadd(ls, g[u].ad, g[u]._ad), pushadd(rs, g[u].ad, g[u]._ad),
        g[u].ad = g[u]._ad = 0;
  if (g[u].st != INT_MIN)
    pushset(ls, g[u].st, g[u]._st), pushset(rs, g[u].st, g[u]._st),
        g[u].st = g[u]._st = INT_MIN;
}
void build(int u = 1, int l = 1, int r = n) {
  g[u]._st = g[u].st = INT_MIN;
  if (l == r) {
    g[u].mx = a[l];
    g[u]._mx = a[l];
    return;
  }
  build(ls, l, mid), build(rs, mid + 1, r);
  pushup(u);
}
int L, R;
void add(int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) return pushadd(u, v, max(v, 0));
  pushdown(u, l, r);
  add(v, ls, l, mid), add(v, rs, mid + 1, r);
  pushup(u);
}
void tset(int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) return pushset(u, v, v);
  pushdown(u, l, r);
  tset(v, ls, l, mid), tset(v, rs, mid + 1, r);
  pushup(u);
}
int qmax(int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return INT_MIN;
  if (L <= l && r <= R) return g[u].mx;
  pushdown(u, l, r);
  return max(qmax(ls, l, mid), qmax(rs, mid + 1, r));
}
int qmaxh(int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return INT_MIN;
  if (L <= l && r <= R) return g[u]._mx;
  pushdown(u, l, r);
  return max(qmaxh(ls, l, mid), qmaxh(rs, mid + 1, r));
}
int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  build();
  int m = rd(), z;
  for (int i = 1; i <= m; ++i) {
    char op = nc();
    while (op == ' ' || op == '\r' || op == '\n') op = nc();
    L = rd(), R = rd();
    if (op == 'Q')
      printf("%d\n", qmax());
    else if (op == 'A')
      printf("%d\n", qmaxh());
    else if (op == 'P')
      add(rd());
    else
      tset(rd());
  }
  return 0;
}

### 主席树

const int maxn = 1e5;  // 数据范围
int tot, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10],
    rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;
inline int getid(const int &val) {  // 离散化
  return lower_bound(ind + 1, ind + len + 1, val) - ind;
}
int build(int l, int r) {  // 建树
  int root = ++tot;
  if (l == r) return root;
  int mid = l + r >> 1;
  ls[root] = build(l, mid);
  rs[root] = build(mid + 1, r);
  return root;  // 返回该子树的根节点
}
int update(int k, int l, int r, int root) {  // 插入操作
  int dir = ++tot;
  ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
  if (l == r) return dir;
  int mid = l + r >> 1;
  if (k <= mid)
    ls[dir] = update(k, l, mid, ls[dir]);
  else
    rs[dir] = update(k, mid + 1, r, rs[dir]);
  return dir;
}
int query(int u, int v, int l, int r, int k) {  // 查询操作
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // 通过区间减法得到左儿子的信息
  if (l == r) return l;
  if (k <= x)  // 说明在左儿子中
    return query(ls[u], ls[v], l, mid, k);
  else  // 说明在右儿子中
    return query(rs[u], rs[v], mid + 1, r, k - x);
}
inline void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  memcpy(ind, a, sizeof ind);
  sort(ind + 1, ind + n + 1);
  len = unique(ind + 1, ind + n + 1) - ind - 1;
  rt[0] = build(1, len);
  for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

### 树链剖分

const int maxn=1e5+5;
struct tree_{
    int tot=0,head[maxn],Next[maxn*2],to[maxn*2];
    int siz[maxn],top[maxn],son[maxn],dep[maxn],fa[maxn],dfn[maxn],rnk[maxn],cnt;
    void init(int n){
        tot=0;
        for (int i=1; i<=n; i++){
            head[i]=-1;
        }
    }
    void add_edge(int a,int b){
        Next[tot]=head[a],to[tot]=b;
        head[a]=tot++;
    }
    void dfs1(int x) {
        son[x]=-1;
        siz[x]=1;
        for (int i=head[x]; i=-1; i=Next[i]){
            int y=to[i];
            if (!dep[y]) {
                dep[y]=dep[x]+1;
                fa[y]=x;
                dfs1(y);
                siz[x]+=siz[y];
                if (son[x]==-1 || siz[y]>siz[son[x]]) son[x]=y;
            }
        }
    }
    void dfs2(int x,int t) {
        top[x]=t;
        cnt++;
        dfn[x]=cnt;
        rnk[cnt]=x;
        if (son[x]==-1) return;
        dfs2(son[x],t);
        for (int i=head[x]; i!=-1; i=Next[i]){
            int y=to[i];
            if (y!=son[x] && y!=fa[x]) dfs2(y,y);
        }
    }
}tr;

## DP优化
### 斜率优化

### 四边形不等式优化

## 数学
### 高精度板子

#include<bits/stdc++.h>
    using namespace std;  
  
    const int maxn = 1000;  
  
    struct bign{  
    int d[maxn], len;  
  
    void clean() { while(len > 1 && !d[len-1]) len--; }  
  
    bign()          { memset(d, 0, sizeof(d)); len = 1; }  
    bign(int num)   { *this = num; }   
    bign(char* num) { *this = num; }  
    bign operator = (const char* num){  
        memset(d, 0, sizeof(d)); len = strlen(num);  
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';  
        clean();  
        return *this;  
    }  
    bign operator = (int num){  
        char s[20]; sprintf(s, "%d", num);  
        *this = s;  
        return *this;  
    }  
  
    bign operator + (const bign& b){  
        bign c = *this; int i;  
        for (i = 0; i < b.len; 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 = i+1;  
        return c;  
    }  
    bign operator - (const bign& b){  
        bign c = *this; int i;  
        for (i = 0; i < b.len; 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]--;  
        c.clean();  
        return c;  
    }  
    bign operator * (const bign& b)const{  
        int i, j; bign c; c.len = len + b.len;   
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)   
            c.d[i+j] += d[i] * b.d[j];  
        for(i = 0; i < c.len-1; i++)  
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;  
        c.clean();  
        return c;  
    }  
    bign operator / (const bign& b){  
        int i, j;  
        bign c = *this, a = 0;  
        for (i = len - 1; i >= 0; i--)  
        {  
            a = a*10 + d[i];  
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;  
            c.d[i] = j;  
            a = a - b*j;  
        }  
        c.clean();  
        return c;  
    }  
    bign operator % (const bign& b){  
        int i, j;  
        bign a = 0;  
        for (i = len - 1; i >= 0; i--)  
        {  
            a = a*10 + d[i];  
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;  
            a = a - b*j;  
        }  
        return a;  
    }  
    bign operator += (const bign& b){  
        *this = *this + b;  
        return *this;  
    }  
  
    bool operator <(const bign& b) const{  
        if(len != b.len) return len < b.len;  
        for(int i = len-1; i >= 0; i--)  
            if(d[i] != b.d[i]) return d[i] < b.d[i];  
        return false;  
    }  
    bool operator >(const bign& b) const{return b < *this;}  
    bool operator<=(const bign& b) const{return !(b < *this);}  
    bool operator>=(const bign& b) const{return !(*this < b);}  
    bool operator!=(const bign& b) const{return b < *this || *this < b;}  
    bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}  
  
    string str() const{  
        char s[maxn]={};  
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';  
        return s;  
    }  
    };  
  
    istream& operator >> (istream& in, bign& x)  
    {  
     string s;  
    in >> s;  
    x = s.c_str();  
    return in;  
    }  
  
    ostream& operator << (ostream& out, const bign& x)  
    {  
    out << x.str();  
    return out;  
    }

### 卡特兰数

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为：
Cat(n) = C(2n, n) / (n + 1)

### 快速幂

ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

### LCM

//lcm
ll lcm(int a, int b)
{
    return a / __gcd(a, b) * b;
}

### 拓展GCD

//扩展gcd
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
    if (a == 0 && b == 0)
        return -1ll;
    if (b == 0)
    {
        x = 1ll;
        y = 0ll;
        return a;
    }
    ll d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

### 求逆元

//逆元 nlogn
ll mod_reverse(ll a, ll n)
{
    ll x, y, d = extend_gcd(a, n, x, y);
    if (d == 1)
    {
        if (x % n <= 0)
            return x % n + n;
        else
            return x % n;
    }
    else
        return -1ll;
}

//逆元 n
int inv[N];
void pre_inv()
{
    inv[1] = 1;
    for (int i = 2; i < mod; i++)
    {
        int a = mod / i, b = mod % i;
        inv[i] = (1LL * inv[b] * (-a) % mod + mod) % mod;
    }
}

### 线性素数筛

bool is_prime[1000100] = {1, 1};
ll prime[100010], cnt = 0;

// 素数线性筛
void euler(int p = 1000100)
{
    for (long long i = 2; i <= p; ++i)
    {
        if (!is_prime[i])
            prime[++cnt] = i;
        for (long long j = 1; j <= cnt && i * prime[j] <= p; ++j)
        {
            is_prime[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

### 自适应辛普森

/*
自适应辛普森，用于连续函数积分
*/
double f(double x)//define the function for yourself!
{}
double simpson(double l, double r)
{
    double mid = (l + r) / 2;
    return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;
}
double asr(double l, double r, double eqs, double ans, int step)
{
    double mid = (l + r) / 2;
    double fl = simpson(l, mid), fr = simpson(mid, r);
    if (abs(fl + fr - ans) <= 15 * eqs && step < 0)
        return fl + fr + (fl + fr - ans) / 15;
    return asr(l, mid, eqs / 2, fl, step - 1) +
           asr(mid, r, eqs / 2, fr, step - 1);
}
double calc(double l, double r, double eps = 1e-8)
{
    return asr(l, r, eps, simpson(l, r), 12);
}

### FFT

class FFT
{
public:
    typedef pair<ll, ll> P;
    typedef complex<double> cp;
    const static ll inf = 0x3f3f3f3f;
    const static int mod = 1e9 + 7;
    const static int maxn = 2e6 + 5;
    const static double pi = 3.14159265;
    int n, m, v;
    int rev[maxn + maxn & (-maxn) + 10], res[maxn + maxn & (-maxn) + 10];
    cp p[maxn + maxn & (-maxn) + 10], q[maxn + maxn & (-maxn) + 10];

    FFT(int n, int m) : n(n), m(m)
    {
        v = 2;
        while (v < n + m)
            v *= 2;
        memset(rev, 0, sizeof(rev));
        memset(res, 0, sizeof(res));
        memset(p, 0, sizeof(p));
        memset(q, 0, sizeof(q));
    }

    void input()
    {
        for (int i = 0; i <= n; i++)
            cin >> p[i];
        for (int i = 0; i <= m; i++)
            cin >> q[i];
    }

    void display()
    {
        for (int i = 0; i <= n + m; i++)
        {
            cout << res[i] << ' ';
        }
        cout << endl;
    }

    void fft(cp *a, int n, int inv)
    {
        int bit = 0;
        while ((1 << bit) < n)
            bit++;
        for (int i = 0; i < n; i++)
        {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
            if (i < rev[i])
                swap(a[i], a[rev[i]]); //不加这条if会交换两次（就是没交换）
        }
        for (int mid = 1; mid < n; mid *= 2) //mid是准备合并序列的长度的二分之一
        {
            cp temp(cos(pi / mid), inv * sin(pi / mid)); //单位根，pi的系数2已经约掉了
            for (int i = 0; i < n; i += mid * 2)         //mid*2是准备合并序列的长度，i是合并到了哪一位
            {
                cp omega(1, 0);
                for (int j = 0; j < mid; j++, omega *= temp) //只扫左半部分，得到右半部分的答案
                {
                    cp x = a[i + j], y = omega * a[i + j + mid];
                    a[i + j] = x + y, a[i + j + mid] = x - y; //这个就是蝴蝶变换什么的
                }
            }
        }
    }
    void multi()
    {
        fft(p, v, 1);
        fft(q, v, 1);
        for (int i = 0; i < v; i++)
            p[i] *= q[i];
        fft(p, v, -1);
        for (int i = 0; i < v; i++)
            res[i] = (int)(p[i].real() / v + 0.5);
    }

    void BigMulti(char *a, char *b, char *&res)
    {
        res = new char[v + 100];
        int ptr = 0;
        for (int i = 0; i <= n; i++)
        {
            p[i] = cp(a[n - i] - '0', 0);
        }
        for (int i = 0; i <= m; i++)
        {
            q[i] = cp(b[m - i] - '0', 0);
        }
        multi();
        int temp = 0;
        for (int i = 0; i <= n + m; i++)
        {
            int now = temp + res[i];
            res[ptr] = char('0' + now % 10);
            ptr++;
            temp = now / 10;
        }
        while (temp)
        {
            res[ptr] = char(temp % 10 + '0');
            ptr++;
            temp /= 10;
        }
    }
};

ll excrt(vector<P> p)
{
    ll m = 0, b = 0;
    for (auto it : p)
    {
        if (b == 0)
        {
            m = it.second;
            b = it.first;
        }
        else
        {
            ll x, y;
            ll a1 = b, a2 = it.first;
            ll m1 = m, m2 = it.second;
            ll gcd = extend_gcd(m1, m2, x, y);
            x = qpow(x, ((a2 - b % m2 + m2) % m2) / gcd, m2 / gcd);
            b += m * x, m *= m2 / gcd;
            b = (b % m + m) % m;
        }
    }
    return b;
}

### 杜教筛

class dujiaoshai
{
    const static ll N = 1e6 + 10, INF = 0x3f3f3f3f, mod = 1e9 + 7;
    ll n, m, p;
    ll phi[N], s[N], prime[N], vis[N], tot, d[N];
    ll qmi(ll a, ll b, ll mod)
    {
        ll res = 1;
        while (b)
        {
            if (b & 1)
                res = res * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return res;
    }
    map<ll, ll> mp;
    ll Mod(ll n, ll mod) { return (n % mod + mod) % mod; }
    ll calc_S(ll n, ll mod)
    {
        if (n < N)
            return s[n];
        if (mp.count(n))
            return mp[n];
        ll ans = Mod(1ll * n * (n + 1) / 2, mod);
        for (ll l = 2, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            ans = Mod((ans - 1ll * (r - l + 1) % mod * calc_S(n / l, mod) % mod) % mod, mod);
        }
        return mp[n] = ans;
    }
    ll calc_d(ll n, ll mod)
    {
        if (n < N)
            return d[n];
        ll ans = 0;
        for (ll l = 1, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            ll sum = (1ll * (r - l + 1) * (r + l) / 2) % mod;
            ll pre = (1ll * (1 + n / l) * (n / l) / 2) % mod;
            ans = Mod(ans + 1ll * sum * pre % mod, mod);
        }
        return ans;
    }
    void init(ll mod)
    {
        phi[1] = 1;
        for (ll i = 2; i < N; i++)
        {
            if (!vis[i])
                prime[++tot] = i, phi[i] = i - 1;
            for (ll j = 1; j <= tot && i * prime[j] < N; j++)
            {
                vis[i * prime[j]] = 1;
                if (i % prime[j] == 0)
                {
                    phi[i * prime[j]] = phi[i] * prime[j];
                    break;
                }
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
        }
        for (ll i = 1; i < N; i++)
            for (ll j = i; j < N; j += i)
                d[j]++;
        for (ll i = 1; i < N; i++)
        {
            d[i] = (d[i - 1] + 1ll * i * d[i] % mod) % mod;
            s[i] = (s[i - 1] + phi[i] % mod) % mod;
        }
    }
};

### 欧拉函数表

//欧拉函数表
int phi[1000000];
void phi_table(int n)
{
    for (int i = 2; i <= n; i++)
        phi[i] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!phi[i])
        {
            for (int j = i; j <= n; j += i)
            {
                if (!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

### 米勒罗宾质数判定
用于1e12+大数质数判定。

//米勒罗宾素数判定
bool millerRabbin(int n)
{
    int a = n - 1, b = 0;
    int s = 100;
    while (a % 2 == 0)
        a /= 2, ++b;
    for (int i = 1, j; i <= s; ++i)
    {
        int x = rand() % (n - 2) + 2, v = qpow(x, a, n);
        if (v == 1 || v == n - 1)
            continue;
        for (j = 0; j < b; ++j)
        {
            v = (long long)v * v % n;
            if (v == n - 1)
                break;
        }
        if (j >= b)
            return 0;
    }
    return 1;
}

### 单个欧拉值

//单个欧拉函数值
int euler_phi(int n)
{
    int m = int(sqrt(n + 0.5));
    int ans = n;
    for (int i = 2; i <= m; i++)
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

### 斐波那契数列相关操作

struct fib
{
    ll ver[2][2];
    fib()
    {
        ver[0][0] = ver[0][1] = ver[1][0] = 1;
    }
    
    
    //快速幂，算F（n+m）
    fib operator*(fib y) const
    {
        fib ans;
        ll res = 0;
        for (ll i = 0; i < 2; i++)
        {
            for (ll j = 0; j < 2; j++)
            {
                res = 0;
                for (ll k = 0; k < 2; k++)
                {
                    res = (res + ver[i][k] * y.ver[k][j] % mod) % mod;
                }
                ans.ver[i][j] = res;
            }
        }
        return ans;
    }
    
    //求第n个斐波那契数
    ll Fib(ll n)
    {
        fib res, a;
        while (n)
        {
            if (n & 1)
                res = res * a;
            a = a * a;
            n >>= 1;
        }
        return res.ver[1][1];
    }
    
    //大数取模
    string p;
    ll Mod(ll mmod)
    {
        ll res = 0;
        for (ll i = 0; i < p.length(); i++)
        {
            res = (res * 10 + p[i] - '0') % mmod;
        }
        return res;
    }
    
    
    //找斐波那契数列循环结
    ll lcm(ll a, ll b)
    {
        return b / __gcd(a, b) * a;
    } 
    ll getLooper(ll v)
    {
        if (v == 5)
            return 20;
        if (v % 5 == 2 || v % 5 == 3)
            return v * 2 + 2;
        return v - 1;
    }
    
    ll getLoop(ll mmod)
    {
        ll ans = 1;
        for (ll i = 1; i <= cnt; i++)
        {
            if (mmod % prime[i] == 0)
            {
                ll v = 1;
                while (mmod % prime[i] == 0)
                    v *= prime[i], mmod /= prime[i];
                ans = lcm(ans, v / prime[i] * getLooper(prime[i]));
            }
        }
        if (mmod != 1)
            ans = lcm(ans, getLooper(mmod));
        return ans;
    }
};

### (拓展)中国剩余定理相关

ll excrt(vector<P> p)
{
    ll m = 0, b = 0;
    for (auto it : p)
    {
        if (b == 0)
        {
            m = it.second;
            b = it.first;
        }
        else
        {
            ll x, y;
            ll a1 = b, a2 = it.first;
            ll m1 = m, m2 = it.second;
            ll gcd = extend_gcd(m1, m2, x, y);
            x = qpow(x, ((a2 - b % m2 + m2) % m2) / gcd, m2 / gcd);
            b += m * x, m *= m2 / gcd;
            b = (b % m + m) % m;
        }
    }
    return b;
}

### 多项式

空间非常优秀但是时间偏慢。

namespace fstdlib
{
    typedef long long ll;
    int mod = 998244353, grt = 3;
    class poly
    {
    private:
        std::vector<int> data;

    public:
        poly(std::size_t len = std::size_t(0)) { data = std::vector<int>(len); }
        poly(const std::vector<int> &b) { data = b; }
        poly(const poly &b) { data = b.data; }
        void resize(std::size_t len, int val = 0) { data.resize(len, val); }
        std::size_t size(void) const { return data.size(); }
        void clear(void) { data.clear(); }
#if __cplusplus >= 201103L
        void shrink_to_fit(void)
        {
            data.shrink_to_fit();
        }
#endif
        void out(void)
        {
            for (int i = 0; i < (int)data.size(); ++i)
                printf("%d ", data[i]);
            puts("");
        }
        int &operator[](std::size_t b)
        {
            return data[b];
        }
        const int &operator[](std::size_t b) const { return data[b]; }
        poly operator*(const poly &h) const;
        poly operator*=(const poly &h);
        poly operator*(const int &h) const;
        poly operator*=(const int &h);
        poly operator+(const poly &h) const;
        poly operator+=(const poly &h);
        poly operator-(const poly &h) const;
        poly operator-=(const poly &h);
        poly operator<<(const std::size_t &b) const;
        poly operator<<=(const std::size_t &b);
        poly operator>>(const std::size_t &b) const;
        poly operator>>=(const std::size_t &b);
        poly operator/(const int &h) const;
        poly operator/=(const int &h);
        poly operator==(const poly &h) const;
        poly operator!=(const poly &h) const;
        poly operator+(const int &h) const;
        poly operator+=(const int &h);
        poly inv(void) const;
        poly inv(const int &h) const;
        friend poly sqrt(const poly &h);
        friend poly log(const poly &h);
        friend poly exp(const poly &h);
    };

    int qpow(int a, int b, int p = mod)
    {
        int res = 1;
        while (b)
        {
            if (b & 1)
                res = (ll)res * a % p;
            a = (ll)a * a % p, b >>= 1;
        }
        return res;
    }

    std::vector<int> rev;
    void dft_for_module(std::vector<int> &f, int n, int b)
    {
        static std::vector<int> w;
        w.resize(n);
        for (int i = 0; i < n; ++i)
            if (i < rev[i])
                std::swap(f[i], f[rev[i]]);
        for (int i = 2; i <= n; i <<= 1)
        {
            w[0] = 1, w[1] = qpow(grt, (mod - 1) / i);
            if (b == -1)
                w[1] = qpow(w[1], mod - 2);
            for (int j = 2; j < i / 2; ++j)
                w[j] = (ll)w[j - 1] * w[1] % mod;
            for (int j = 0; j < n; j += i)
                for (int k = 0; k < i / 2; ++k)
                {
                    int p = f[j + k], q = (ll)f[j + k + i / 2] * w[k] % mod;
                    f[j + k] = (p + q) % mod, f[j + k + i / 2] = (p - q + mod) % mod;
                }
        }
    }

    poly poly::operator*(const poly &h) const
    {
        int N = 1;
        while (N < (int)(size() + h.size() - 1))
            N <<= 1;
        std::vector<int> f(this->data), g(h.data);
        f.resize(N), g.resize(N);
        rev.resize(N);
        for (int i = 0; i < N; ++i)
            rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
        dft_for_module(f, N, 1), dft_for_module(g, N, 1);
        for (int i = 0; i < N; ++i)
            f[i] = (ll)f[i] * g[i] % mod;
        dft_for_module(f, N, -1), f.resize(size() + h.size() - 1);
        for (int i = 0, inv = qpow(N, mod - 2); i < (int)f.size(); ++i)
            f[i] = (ll)f[i] * inv % mod;
        return f;
    }

    poly poly::operator*=(const poly &h) { return *this = *this * h; }

    poly poly::operator*(const int &h) const
    {
        std::vector<int> f(this->data);
        for (int i = 0; i < (int)f.size(); ++i)
            f[i] = (ll)f[i] * h % mod;
        return f;
    }

    poly poly::operator*=(const int &h)
    {
        for (int i = 0; i < (int)size(); ++i)
            data[i] = (ll)data[i] * h % mod;
        return *this;
    }

    poly poly::operator+(const poly &h) const
    {
        std::vector<int> f(this->data);
        if (f.size() < h.size())
            f.resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            f[i] = (f[i] + h[i]) % mod;
        return f;
    }

    poly poly::operator+=(const poly &h)
    {
        std::vector<int> &f = this->data;
        if (f.size() < h.size())
            f.resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            f[i] = (f[i] + h[i]) % mod;
        return f;
    }

    poly poly::operator-(const poly &h) const
    {
        std::vector<int> f(this->data);
        if (f.size() < h.size())
            f.resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            f[i] = (f[i] - h[i] + mod) % mod;
        return f;
    }

    poly poly::operator-=(const poly &h)
    {
        std::vector<int> &f = this->data;
        if (f.size() < h.size())
            f.resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            f[i] = (f[i] - h[i] + mod) % mod;
        return f;
    }

    poly poly::operator<<(const std::size_t &b) const
    {
        std::vector<int> f(size() + b);
        for (int i = 0; i < (int)size(); ++i)
            f[i + b] = data[i];
        return f;
    }

    poly poly::operator<<=(const std::size_t &b) { return *this = (*this) << b; }

    poly poly::operator>>(const std::size_t &b) const
    {
        std::vector<int> f(size() - b);
        for (int i = 0; i < (int)f.size(); ++i)
            f[i] = data[i + b];
        return f;
    }

    poly poly::operator>>=(const std::size_t &b) { return *this = (*this) >> b; }

    poly poly::operator/(const int &h) const
    {
        std::vector<int> f(this->data);
        int inv = qpow(h, mod - 2);
        for (int i = 0; i < (int)f.size(); ++i)
            f[i] = (ll)f[i] * inv % mod;
        return f;
    }

    poly poly::operator/=(const int &h)
    {
        int inv = qpow(h, mod - 2);
        for (int i = 0; i < (int)data.size(); ++i)
            data[i] = (ll)data[i] * inv % mod;
        return *this;
    }

    poly poly::inv(void) const
    {
        int N = 1;
        while (N < (int)(size() + size() - 1))
            N <<= 1;
        std::vector<int> f(N), g(N), d(this->data);
        d.resize(N), f[0] = qpow(d[0], mod - 2);
        for (int w = 2; w < N; w <<= 1)
        {
            for (int i = 0; i < w; ++i)
                g[i] = d[i];
            rev.resize(w << 1);
            for (int i = 0; i < w * 2; ++i)
                rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? w : 0);
            dft_for_module(f, w << 1, 1), dft_for_module(g, w << 1, 1);
            for (int i = 0; i < w * 2; ++i)
                f[i] = (ll)f[i] * (2 + mod - (ll)f[i] * g[i] % mod) % mod;
            dft_for_module(f, w << 1, -1);
            for (int i = 0, inv = qpow(w << 1, mod - 2); i < w; ++i)
                f[i] = (ll)f[i] * inv % mod;
            for (int i = w; i < w * 2; ++i)
                f[i] = 0;
        }
        f.resize(size());
        return f;
    }

    poly poly::operator==(const poly &h) const
    {
        if (size() != h.size())
            return 0;
        for (int i = 0; i < (int)size(); ++i)
            if (data[i] != h[i])
                return 0;
        return 1;
    }

    poly poly::operator!=(const poly &h) const
    {
        if (size() != h.size())
            return 1;
        for (int i = 0; i < (int)size(); ++i)
            if (data[i] != h[i])
                return 1;
        return 0;
    }

    poly poly::operator+(const int &h) const
    {
        poly f(this->data);
        f[0] = (f[0] + h) % mod;
        return f;
    }

    poly poly::operator+=(const int &h) { return *this = (*this) + h; }

    poly poly::inv(const int &h) const
    {
        poly f(*this);
        f.resize(h);
        return f.inv();
    }
    int modsqrt(int h, int p = mod) { return 1; }

    poly sqrt(const poly &h)
    {
        int N = 1;
        while (N < (int)(h.size() + h.size() - 1))
            N <<= 1;
        poly f(N), g(N), d(h);
        d.resize(N), f[0] = modsqrt(d[0]);
        for (int w = 2; w < N; w <<= 1)
        {
            g.resize(w);
            for (int i = 0; i < w; ++i)
                g[i] = d[i];
            f = (f + f.inv(w) * g) / 2;
            f.resize(w);
        }
        f.resize(h.size());
        return f;
    }

    poly log(const poly &h)
    {
        poly f(h);
        for (int i = 1; i < (int)f.size(); ++i)
            f[i - 1] = (ll)f[i] * i % mod;
        f[f.size() - 1] = 0, f = f * h.inv(), f.resize(h.size());
        for (int i = (int)f.size() - 1; i > 0; --i)
            f[i] = (ll)f[i - 1] * qpow(i, mod - 2) % mod;
        f[0] = 0;
        return f;
    }

    poly exp(const poly &h)
    {
        int N = 1;
        while (N < (int)(h.size() + h.size() - 1))
            N <<= 1;
        poly f(N), g(N), d(h);
        f[0] = 1, d.resize(N);
        for (int w = 2; w < N; w <<= 1)
        {
            f.resize(w), g.resize(w);
            for (int i = 0; i < w; ++i)
                g[i] = d[i];
            f = f * (g + 1 - log(f));
            f.resize(w);
        }
        f.resize(h.size());
        return f;
    }

    struct comp
    {
        long double x, y;
        comp(long double _x = 0, long double _y = 0) : x(_x), y(_y) {}
        comp operator*(const comp &b) const
        {
            return comp(x * b.x - y * b.y, x * b.y + y * b.x);
        }
        comp operator+(const comp &b) const { return comp(x + b.x, y + b.y); }
        comp operator-(const comp &b) const { return comp(x - b.x, y - b.y); }
        comp conj(void) { return comp(x, -y); }
    };

    const int EPS = 1e-9;

    template <typename FLOAT_T>
    FLOAT_T fabs(const FLOAT_T &x)
    {
        return x > 0 ? x : -x;
    }

    template <typename FLOAT_T>
    FLOAT_T sin(const FLOAT_T &x, const long double &EPS = fstdlib::EPS)
    {
        FLOAT_T res = 0, delt = x;
        int d = 0;
        while (fabs(delt) > EPS)
        {
            res += delt, ++d;
            delt *= -x * x / ((2 * d) * (2 * d + 1));
        }
        return res;
    }

    template <typename FLOAT_T>
    FLOAT_T cos(const FLOAT_T &x, const long double &EPS = fstdlib::EPS)
    {
        FLOAT_T res = 0, delt = 1;
        int d = 0;
        while (fabs(delt) > EPS)
        {
            res += delt, ++d;
            delt *= -x * x / ((2 * d) * (2 * d - 1));
        }
        return res;
    }

    const long double PI = std::acos((long double)(-1));

    void dft_for_complex(std::vector<comp> &f, int n, int b)
    {
        static std::vector<comp> w;
        w.resize(n);
        for (int i = 0; i < n; ++i)
            if (i < rev[i])
                std::swap(f[i], f[rev[i]]);
        for (int i = 2; i <= n; i <<= 1)
        {
            w[0] = comp(1, 0), w[1] = comp(cos(2 * PI / i), b * sin(2 * PI / i));
            for (int j = 2; j < i / 2; ++j)
                w[j] = w[j - 1] * w[1];
            for (int j = 0; j < n; j += i)
                for (int k = 0; k < i / 2; ++k)
                {
                    comp p = f[j + k], q = f[j + k + i / 2] * w[k];
                    f[j + k] = p + q, f[j + k + i / 2] = p - q;
                }
        }
    }

    class arbitrary_module_poly
    {
    private:
        std::vector<int> data;
        int construct_element(int D, ll x, ll y, ll z) const
        {
            x %= mod, y %= mod, z %= mod;
            return ((ll)D * D * x % mod + (ll)D * y % mod + z) % mod;
        }

    public:
        int mod;
        arbitrary_module_poly(std::size_t len = std::size_t(0),
                              int module_value = 1e9 + 7)
        {
            mod = module_value;
            data = std::vector<int>(len);
        }
        arbitrary_module_poly(const std::vector<int> &b, int module_value = 1e9 + 7)
        {
            mod = module_value;
            data = b;
        }
        arbitrary_module_poly(const arbitrary_module_poly &b)
        {
            mod = b.mod;
            data = b.data;
        }
        void resize(std::size_t len, const int &val = 0) { data.resize(len, val); }
        std::size_t size(void) const { return data.size(); }
        void clear(void) { data.clear(); }
#if __cplusplus >= 201103L
        void shrink_to_fit(void)
        {
            data.shrink_to_fit();
        }
#endif
        int &operator[](std::size_t b)
        {
            return data[b];
        }
        const int &operator[](std::size_t b) const { return data[b]; }
        arbitrary_module_poly operator*(const arbitrary_module_poly &h) const;
        arbitrary_module_poly operator*=(const arbitrary_module_poly &h);
        arbitrary_module_poly operator*(const int &h) const;
        arbitrary_module_poly operator*=(const int &h);
        arbitrary_module_poly operator+(const arbitrary_module_poly &h) const;
        arbitrary_module_poly operator+=(const arbitrary_module_poly &h);
        arbitrary_module_poly operator-(const arbitrary_module_poly &h) const;
        arbitrary_module_poly operator-=(const arbitrary_module_poly &h);
        arbitrary_module_poly operator<<(const std::size_t &b) const;
        arbitrary_module_poly operator<<=(const std::size_t &b);
        arbitrary_module_poly operator>>(const std::size_t &b) const;
        arbitrary_module_poly operator>>=(const std::size_t &b);
        arbitrary_module_poly operator/(const int &h) const;
        arbitrary_module_poly operator/=(const int &h);
        arbitrary_module_poly operator==(const arbitrary_module_poly &h) const;
        arbitrary_module_poly operator!=(const arbitrary_module_poly &h) const;
        arbitrary_module_poly inv(void) const;
        arbitrary_module_poly inv(const int &h) const;
        friend arbitrary_module_poly sqrt(const arbitrary_module_poly &h);
        friend arbitrary_module_poly log(const arbitrary_module_poly &h);
    };

    arbitrary_module_poly arbitrary_module_poly::operator*(
        const arbitrary_module_poly &h) const
    {
        int N = 1;
        while (N < (int)(size() + h.size() - 1))
            N <<= 1;
        std::vector<comp> f(N), g(N), p(N), q(N);
        const int D = std::sqrt(mod);
        for (int i = 0; i < (int)size(); ++i)
            f[i].x = data[i] / D, f[i].y = data[i] % D;
        for (int i = 0; i < (int)h.size(); ++i)
            g[i].x = h[i] / D, g[i].y = h[i] % D;
        rev.resize(N);
        for (int i = 0; i < N; ++i)
            rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
        dft_for_complex(f, N, 1), dft_for_complex(g, N, 1);
        for (int i = 0; i < N; ++i)
        {
            p[i] = (f[i] + f[(N - i) % N].conj()) * comp(0.50, 0) * g[i];
            q[i] = (f[i] - f[(N - i) % N].conj()) * comp(0, -0.5) * g[i];
        }
        dft_for_complex(p, N, -1), dft_for_complex(q, N, -1);
        std::vector<int> r(size() + h.size() - 1);
        for (int i = 0; i < (int)r.size(); ++i)
            r[i] = construct_element(D, p[i].x / N + 0.5, (p[i].y + q[i].x) / N + 0.5,
                                     q[i].y / N + 0.5);
        return arbitrary_module_poly(r, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator*=(
        const arbitrary_module_poly &h)
    {
        return *this = *this * h;
    }

    arbitrary_module_poly arbitrary_module_poly::operator*(const int &h) const
    {
        std::vector<int> f(this->data);
        for (int i = 0; i < (int)f.size(); ++i)
            f[i] = (ll)f[i] * h % mod;
        return arbitrary_module_poly(f, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator*=(const int &h)
    {
        for (int i = 0; i < (int)size(); ++i)
            data[i] = (ll)data[i] * h % mod;
        return *this;
    }

    arbitrary_module_poly arbitrary_module_poly::operator+(
        const arbitrary_module_poly &h) const
    {
        std::vector<int> f(this->data);
        if (f.size() < h.size())
            f.resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            f[i] = (f[i] + h[i]) % mod;
        return arbitrary_module_poly(f, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator+=(
        const arbitrary_module_poly &h)
    {
        if (size() < h.size())
            resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            data[i] = (data[i] + h[i]) % mod;
        return *this;
    }

    arbitrary_module_poly arbitrary_module_poly::operator-(
        const arbitrary_module_poly &h) const
    {
        std::vector<int> f(this->data);
        if (f.size() < h.size())
            f.resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            f[i] = (f[i] + mod - h[i]) % mod;
        return arbitrary_module_poly(f, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator-=(
        const arbitrary_module_poly &h)
    {
        if (size() < h.size())
            resize(h.size());
        for (int i = 0; i < (int)h.size(); ++i)
            data[i] = (data[i] + mod - h[i]) % mod;
        return *this;
    }

    arbitrary_module_poly arbitrary_module_poly::operator<<(
        const std::size_t &b) const
    {
        std::vector<int> f(size() + b);
        for (int i = 0; i < (int)size(); ++i)
            f[i + b] = data[i];
        return arbitrary_module_poly(f, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator<<=(const std::size_t &b)
    {
        return *this = (*this) << b;
    }

    arbitrary_module_poly arbitrary_module_poly::operator>>(
        const std::size_t &b) const
    {
        std::vector<int> f(size() - b);
        for (int i = 0; i < (int)f.size(); ++i)
            f[i] = data[i + b];
        return arbitrary_module_poly(f, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator>>=(const std::size_t &b)
    {
        return *this = (*this) >> b;
    }

    arbitrary_module_poly arbitrary_module_poly::inv(void) const
    {
        int N = 1;
        while (N < (int)(size() + size() - 1))
            N <<= 1;
        arbitrary_module_poly f(1, mod), g(N, mod), h(*this), f2(1, mod);
        f[0] = qpow(data[0], mod - 2, mod), h.resize(N), f2[0] = 2;
        for (int w = 2; w < N; w <<= 1)
        {
            g.resize(w);
            for (int i = 0; i < w; ++i)
                g[i] = h[i];
            f = f * (f * g - f2) * (mod - 1);
            f.resize(w);
        }
        f.resize(size());
        return f;
    }

    arbitrary_module_poly arbitrary_module_poly::inv(const int &h) const
    {
        arbitrary_module_poly f(*this);
        f.resize(h);
        return f.inv();
    }

    arbitrary_module_poly arbitrary_module_poly::operator/(const int &h) const
    {
        int inv = qpow(h, mod - 2, mod);
        std::vector<int> f(this->data);
        for (int i = 0; i < (int)f.size(); ++i)
            f[i] = (ll)f[i] * inv % mod;
        return arbitrary_module_poly(f, mod);
    }

    arbitrary_module_poly arbitrary_module_poly::operator/=(const int &h)
    {
        int inv = qpow(h, mod - 2, mod);
        for (int i = 0; i < (int)size(); ++i)
            data[i] = (ll)data[i] * inv % mod;
        return *this;
    }

    arbitrary_module_poly arbitrary_module_poly::operator==(
        const arbitrary_module_poly &h) const
    {
        if (size() != h.size() || mod != h.mod)
            return 0;
        for (int i = 0; i < (int)size(); ++i)
            if (data[i] != h[i])
                return 0;
        return 1;
    }

    arbitrary_module_poly arbitrary_module_poly::operator!=(
        const arbitrary_module_poly &h) const
    {
        if (size() != h.size() || mod != h.mod)
            return 1;
        for (int i = 0; i < (int)size(); ++i)
            if (data[i] != h[i])
                return 1;
        return 0;
    }

    arbitrary_module_poly sqrt(const arbitrary_module_poly &h)
    {
        int N = 1;
        while (N < (int)(h.size() + h.size() - 1))
            N <<= 1;
        arbitrary_module_poly f(1, mod), g(N, mod), d(h);
        f[0] = modsqrt(h[0], mod), d.resize(N);
        for (int w = 2; w < N; w <<= 1)
        {
            g.resize(w);
            for (int i = 0; i < w; ++i)
                g[i] = d[i];
            f = (f + f.inv(w) * g) / 2;
            f.resize(w);
        }
        f.resize(h.size());
        return f;
    }

    arbitrary_module_poly log(const arbitrary_module_poly &h)
    {
        arbitrary_module_poly f(h);
        for (int i = 1; i < (int)f.size(); ++i)
            f[i - 1] = (ll)f[i] * i % f.mod;
        f[f.size() - 1] = 0, f = f * h.inv(), f.resize(h.size());
        for (int i = (int)f.size() - 1; i > 0; --i)
            f[i] = (ll)f[i - 1] * qpow(i, f.mod - 2, f.mod) % f.mod;
        f[0] = 0;
        return f;
    }
    typedef arbitrary_module_poly m_poly;
} 
// namespace fstdlib

## 计算几何

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
int Equal(double x)
{
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    else
        return 1;
}
struct Point
{
    double x, y;
    Point() {}
    Point(double _x, double _y)
    {
        x = _x;
        y = _y;
    }
    void input() { scanf("%lf%lf", &x, &y); }
    void output() { printf("%.10lf %.10lf\n", x, y); }
    bool operator==(Point b) const { return Equal(x - b.x) == 0 && Equal(y - b.y) == 0; }
    Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
    double operator^(const Point &b) const { return x * b.y - y * b.x; }
    double operator*(const Point &b) const { return x * b.x + y * b.y; }
    Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
    Point operator*(const double &k) const { return Point(x * k, y * k); }
    Point operator/(const double &k) const { return Point(x / k, y / k); }
    double dis(Point p) { return hypot(x - p.x, y - p.y); }
    double angle()
    //极角排序
    {
        double res = atan2(1.0 * y, 1.0 * x) * 180.0 / pi;
        if (res < -eps)
            res = 360.0 + res;
        return res;
    }
};
bool cmp(Point a, Point b)
{
    return a.angle() < b.angle();
}
struct Line
{
    Point s, e;
    Line() {}
    Line(Point _s, Point _e)
    {
        s = _s;
        e = _e;
    }
    bool pointonseg(Point p)
    {
        return Equal((p - s) ^ (e - s)) == 0 && Equal((p - s) * (p - e)) <= 0;
    } //something 叉积精度问题。
    
    
    //计算两条线交点
    Point crosspoint(Line v)
    {
        double a1 = (v.e - v.s) ^ (s - v.s);
        double a2 = (v.e - v.s) ^ (e - v.s);
        return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
    }
};


//三维模拟退火，删除z变成二维
class MidPoint
{
    const double eps = 1e-6;
    double dis[110];
    struct node
    {
        double x;
        double y;
        double z;
        node(){};
        node(double x, double y, double z) : x(x), y(y), z(z){};
        double dis(const node &p)
        {
            double _x = x - p.x, _y = y - p.y, _z = z - p.z;
            return sqrt(_x * _x + _y * _y + _z * _z);
        }
    } p[110];
    
    //仅仅用于模拟退火
    double solve(int n)
    {
        for (int i = 1; i <= n; i++)
            cin >> p[i].x >> p[i].y >> p[i].z;
        node ans(0.0, 0.0, 0.0);
        for (int i = 1; i <= n; i++)
        {
            ans.x += p[i].x;
            ans.y += p[i].y;
            ans.z += p[i].z;
        }
        ans.x /= n, ans.y /= n, ans.z /= n;
        double mmax = 0;
        int ptr = 0;
        for (int tt = 0; tt <= 100000; tt++)
        {
            for (int i = 1; i <= n; i++)
            {
                dis[i] = ans.dis(p[i]);
                if (dis[i] > mmax)
                    mmax = dis[i], ptr = i;
            }
            mmax /= 10000 * sqrt(3);
            double _x = p[ptr].x - ans.x;
            double _y = p[ptr].y - ans.y;
            double _z = p[ptr].z - ans.z;
            double v = (fabs(_x) + fabs(_y) + fabs(_z));
            ans.x += mmax * _x / v;
            ans.y += mmax * _y / v;
            ans.z += mmax * _z / v;
        }
        double r = 0;
        for (int i = 1; i <= n; i++)
        {
            r = max(r, dis[i]);
        }
        return r;
    }
};


//凸包裸板子
Point p[111111];
bool used[111111];
Point h[111111];
void convex(int n)
{
    int *stk = new int[n + 1];
    int tp = 0;                  // 初始化栈
    std::sort(p + 1, p + 1 + n); // 对点进行排序
    stk[++tp] = 1;
    for (int i = 2; i <= n; ++i)
    {
        while (tp >= 2 && ((p[stk[tp]] - p[stk[tp - 1]]) ^ (p[i] - p[stk[tp]])) <= 0)
            used[stk[tp--]] = 0;
        used[i] = 1;
        stk[++tp] = i;
    }
    int tmp = tp;
    for (int i = n - 1; i > 0; --i)
        if (!used[i])
        {
            while (tp > tmp && ((p[stk[tp]] - p[stk[tp - 1]]) ^ (p[i] - p[stk[tp]])) <= 0)
                used[stk[tp--]] = 0;
            used[i] = 1;
            stk[++tp] = i;
        }
    for (int i = 1; i <= tp; ++i)
        h[i] = p[stk[i]];
    int ans = tp - 1;
}

### 扫描线模板

## 字符串

### 哈希

struct Hash{
    int base[4], mod[4];
    int tot, hash[4][maxn], pw[4][maxn]; //字符串长度,hash:记从1~i的hash值，pw:记录base^i
    Hash(){
        tot = 0;
        for (int i = 1; i <= 3; i++)
            pw[i][0] = 1;
        base[1] = 233;
        base[2] = 19260817;
        base[3] = 20030714;
        mod[1] = 1e9 + 7;
        mod[2] = 1e9 + 9;
        mod[3] = 998244353;
    }
    void init(){
        tot = 0;
    }
    void insert(int c){
        tot++;
        for (int i = 1; i <= 3; i++)
            hash[i][tot] = (1LL * hash[i][tot - 1] * base[i] + c) % mod[i];
        for (int i = 1; i <= 3; i++)
            pw[i][tot] = (1LL * pw[i][tot - 1] * base[i]) % mod[i];
    }
    //字符串[l,r]hash值,type为第几个hash
    int query(int l, int r, int type){
        return (hash[type][r] - (1LL * hash[type][l - 1] * pw[type][r - l + 1] % mod[type]) + mod[type]) % mod[type];
    }
    //判断字符串u的[lu,ru]内的字符串和字符串v的[lv,rv]内的字符串是否相同
    friend bool same(Hash &u, int lu, int ru, Hash &v, int lv, int rv){
        if (ru - lu != rv - lv)
            return false;
        for (int i = 1; i <= 3; i++)
            if (u.query(lu, ru, i) != v.query(lv, rv, i))
                return false;
        return true;
    }
}h;

### NE数组运用

const int N = 1e6 + 7; //字符串长度
int Next[N];
//next 数组的多种应用
void Next_init(int len, char *str)
{
    int i = 1, j = -1;
    Next[0] = -1;
    for (; i < len; Next[i++] = j)
    {
        while (j != -1 && str[j + 1] != str[i])
            j = Next[j];
        if (str[j + 1] == str[i])
            j++;
    }
    for (i = 0; i < len; i++)
    {
        Next[i]++;
    }
}
void show_next(int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << i << ":" << Next[i] << endl;
    }
}
//增加最少的字母使之成为一个非平凡循环串
int min_add_to_cycle(int len, char *str)
{
    Next_init(len, str);
    int L = len - Next[len - 1];
    if (L < len && len % L == 0)
    {
        return 0;
    }
    else
        return L - len % L;
}
//内循环节数量
int cycle_cnt(int len, char *str)
{
    Next_init(len, str);
    return len % (len - Next[len - 1]) ? 1 : len / (len - Next[len - 1]);
}
// 同时是母串前缀和后缀的字符串的长度
vector<int> substring_of_head_and_tail(int len, char *str)
{
    Next_init(len, str);
    vector<int> res;
    res.clear();
    int i = len - 1;
    for (i = Next[i]; i; i = Next[i - 1])
    {
        if (str[i - 1] == str[len - 1])
            res.push_back(i);
    }
    return res;
}
//前一个串的后缀和后一个串的前缀的最大匹配
int max_insert_of_two_string(char *a, char *b, int len_a, int len_b)
{
    char *str = new char[len_a + len_b];
    int len = len_a + len_b;
    for (int i = 0; i < len_a; i++)
        str[i] = a[i];
    for (int i = len_a; i < len; i++)
        str[i] = b[i - len_a];
    Next_init(len, str);
    int i = Next[len - 1];
    for (; i >= min(len_a, len_b);)
        i = Next[i];
    return i;
} //KMP YES!
//不需要注释的kmp,返回所有匹配位置，下标从1开始//KMP YES!
vector<int> KMP(char *a, char *b, int len_a, int len_b)    //KMP YES!
{                                                          //KMP YES!
    Next_init(len_a, a);                                   //KMP YES!
    vector<int> res;                                       //KMP YES!
    res.clear();                                           //KMP YES!
    int i = 0, j = 0;                                      //KMP YES!
    for (; i < len_b; i++)                                 //KMP YES!
    {                                                      //KMP YES!
        while (j && a[j] != b[i])                          //KMP YES!
            j = Next[j - 1];                               //KMP YES!
        if (a[j] == b[i])                                  //KMP YES!
            j++;                                           //KMP YES!
        if (j == len_a)                                    //KMP YES!
            res.push_back(i - len_a + 2), j = Next[j - 1]; //KMP YES!
    }                                                      //KMP YES!
    return res;                                            //KMP YES!
} //KMP YES!

const int maxn = 50 * 1000 + 100; //单词长度*单词数
const int maxlen = 2e6 + 100;     //主串长度
const int maxc = 128;             //树分支数
int n;
int ans[1005];
//在trie上添加后缀结点
//后缀结点：x的后缀结点为非x结点y，y的路径字符串为x的路径字符串的最长后缀且y的路径字符串是单词
struct ac_au
{
    int child[maxn][maxc]; //trie
    int fail[maxn];        //后缀结点
    int sta[maxn];         //该路径字符串单词有无，有存编号
    int cnt;               //结点的个数
    int root;
    int newnode()
    {
        for (int i = 0; i < maxc; i++)
            child[cnt][i] = -1;
        sta[cnt++] = 0;
        return cnt - 1;
    }
    void init()
    {
        cnt = 0;
        root = newnode();
    }
    void insert(char *s, int id) //trie构建
    {
        int len = strlen(s), p = 0;
        for (int i = 0; i < len; i++)
        {
            int c = s[i];
            int &num = child[p][c];
            if (num == -1)
                num = newnode();
            p = num;
        }
        sta[p] = id;
    }
    void build() //后缀结点的添加
    {
        int p = 0;
        queue<int> que;
        fail[p] = p;
        for (int i = 0; i < maxc; i++)
        {
            int &num = child[p][i];
            if (num == -1)
                num = p; //为下文铺垫，和树意义无关
            else
            {
                fail[num] = p; //有点多余，初始化都是0，理解算法过程有用
                que.push(num);
            }
        }
        while (!que.empty())
        {
            p = que.front();
            que.pop();
            for (int i = 0; i < maxc; i++)
            {
                int &num = child[p][i];
                if (num == -1)
                    num = child[fail[p]][i];
                else
                {
                    fail[num] = child[fail[p]][i];
                    que.push(num);
                }
            }
        }
    }
    void query(char *s) //解决多模式串匹配单主串问题
    {
        int len = strlen(s), p = 0;
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < len; i++)
        {
            int c = s[i];
            p = child[p][c];
            int tmp = p;
            while (tmp)
            {
                if (sta[tmp])
                    ans[sta[tmp]]++;
                tmp = fail[tmp];
            }
        }
    }
} ac;

### 后缀数组

## 用到的数学公式

### n·1+(n-1)·2+(n-2)·3+...+2·(n-1)+1·n

ans=**n(n+1)(n+2)/6**

### 连续自然数平方和公式

ans=**n(n+1)(2n+1)/6**

## 离线算法

### CDQ 3维偏序

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int sum[maxn];
int n,cnt=0;
ll res=0;
map<int,int> mp;
struct node{
    int a,b;
}x[maxn],c[maxn];
bool cmp(node x,node y){
    return x.a<y.a;
}
inline int lowbit(int x) { return x & (-x); }
void add(int k, int v) {
    while (k <= cnt) {
        sum[k] += v;
        k += lowbit(k);
    }
}
int getsum(int k) {
    int ret = 0;
    while (k) {
        ret += sum[k];
        k -= lowbit(k);
    }
    return ret;
}
void solve(int l,int r){
    if (l==r) return ;
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    memcpy(c,x,sizeof(x));
    for (int i=0; i<=cnt; i++){
        sum[i]=0;
    }
    sort(c+l,c+mid+1,cmp);
    sort(c+mid+1,c+r+1,cmp);
    int ed=l-1;
    for (int i=mid+1; i<=r; i++){
        while (c[ed+1].a<c[i].a && ed+1<=mid){
            ed++;
            add(mp[c[ed].b],1);
        }
        res+=getsum(mp[c[i].b]-1);
    }
}
vector<int> cc;
int main(){
    scanf("%d",&n);
    cnt=0;
    for (int i=1; i<=n; i++){
        scanf("%d%d",&x[i].a,&x[i].b);
        cc.push_back(x[i].b);
    }
    sort(cc.begin(),cc.end());
    for (auto i:cc){
        if (mp[i]==0) mp[i]=++cnt;
    }
    solve(1,n);
    printf("%lld",res);
}

### 莫队

#### 普通莫队

#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 50005;
int n, m, maxn;
int c[N];
long long sum;
int cnt[N];
long long ans1[N], ans2[N];
struct query {
  int l, r, id;
  bool operator<(const query &x) const {
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];
void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}
void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int main() {
  scanf("%d%d", &n, &m);
  maxn = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  for (int i = 0; i < m; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
      continue;
    }
    while (l > a[i].l) add(c[--l]);
    while (r < a[i].r) add(c[++r]);
    while (l < a[i].l) del(c[l++]);
    while (r > a[i].r) del(c[r--]);
    ans1[a[i].id] = sum;
    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      long long g = gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    printf("%lld/%lld\n", ans1[i], ans2[i]);
  }
  return 0;
}

#### 带修改莫队

#include <bits/stdc++.h>
#define SZ (10005)
using namespace std;
template <typename _Tp>
inline void IN(_Tp& dig) {
  char c;
  dig = 0;
  while (c = getchar(), !isdigit(c))
    ;
  while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}
int n, m, sqn, c[SZ], ct[SZ], c1, c2, mem[SZ][3], ans, tot[1000005], nal[SZ];
struct query {
  int l, r, i, c;
  bool operator<(const query another) const {
    if (l / sqn == another.l / sqn) {
      if (r / sqn == another.r / sqn) return i < another.i;
      return r < another.r;
    }
    return l < another.l;
  }
} Q[SZ];
void add(int a) {
  if (!tot[a]) ans++;
  tot[a]++;
}
void del(int a) {
  tot[a]--;
  if (!tot[a]) ans--;
}
char opt[10];
int main() {
  IN(n), IN(m), sqn = pow(n, (double)2 / (double)3);
  for (int i = 1; i <= n; i++) IN(c[i]), ct[i] = c[i];
  for (int i = 1, a, b; i <= m; i++)
    if (scanf("%s", opt), IN(a), IN(b), opt[0] == 'Q')
      Q[c1].l = a, Q[c1].r = b, Q[c1].i = c1, Q[c1].c = c2, c1++;
    else
      mem[c2][0] = a, mem[c2][1] = ct[a], mem[c2][2] = ct[a] = b, c2++;
  sort(Q, Q + c1), add(c[1]);
  int l = 1, r = 1, lst = 0;
  for (int i = 0; i < c1; i++) {
    for (; lst < Q[i].c; lst++) {
      if (l <= mem[lst][0] && mem[lst][0] <= r)
        del(mem[lst][1]), add(mem[lst][2]);
      c[mem[lst][0]] = mem[lst][2];
    }
    for (; lst > Q[i].c; lst--) {
      if (l <= mem[lst - 1][0] && mem[lst - 1][0] <= r)
        del(mem[lst - 1][2]), add(mem[lst - 1][1]);
      c[mem[lst - 1][0]] = mem[lst - 1][1];
    }
    for (++r; r <= Q[i].r; r++) add(c[r]);
    for (--r; r > Q[i].r; r--) del(c[r]);
    for (--l; l >= Q[i].l; l--) add(c[l]);
    for (++l; l < Q[i].l; l++) del(c[l]);
    nal[Q[i].i] = ans;
  }
  for (int i = 0; i < c1; i++) printf("%d\n", nal[i]);
  return 0;
}

#### 回滚莫队

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;

struct Query {
  int l, r, id;
} Q[N];
int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];

inline bool cmp(const Query& A, const Query& B) {
  if (pos[A.l] == pos[B.l]) return A.r < B.r;
  return pos[A.l] < pos[B.l];
}

void build() {
  sz = sqrt(n);
  tot = n / sz;
  for (int i = 1; i <= tot; i++) {
    L[i] = (i - 1) * sz + 1;
    R[i] = i * sz;
  }
  if (R[tot] < n) {
    ++tot;
    L[tot] = R[tot - 1] + 1;
    R[tot] = n;
  }
}

inline void Add(int v, ll& Ans) {
  ++cnt[v];
  Ans = max(Ans, 1LL * cnt[v] * t[v]);
}

inline void Del(int v) { --cnt[v]; }

int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &x[i]), t[++m] = x[i];
  for (int i = 1; i <= q; i++) scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;

  build();

  // 对询问进行排序
  for (int i = 1; i <= tot; i++)
    for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
  sort(Q + 1, Q + 1 + q, cmp);

  // 离散化
  sort(t + 1, t + 1 + m);
  m = unique(t + 1, t + 1 + m) - (t + 1);
  for (int i = 1; i <= n; i++) x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;

  int l = 1, r = 0, last_block = 0, __l;
  ll Ans = 0, tmp;
  for (int i = 1; i <= q; i++) {
    // 询问的左右端点同属于一个块则暴力扫描回答
    if (pos[Q[i].l] == pos[Q[i].r]) {
      for (int j = Q[i].l; j <= Q[i].r; j++) ++__cnt[x[j]];
      for (int j = Q[i].l; j <= Q[i].r; j++)
        ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
      for (int j = Q[i].l; j <= Q[i].r; j++) --__cnt[x[j]];
      continue;
    }

    // 访问到了新的块则重新初始化莫队区间
    if (pos[Q[i].l] != last_block) {
      while (r > R[pos[Q[i].l]]) Del(x[r]), --r;
      while (l < R[pos[Q[i].l]] + 1) Del(x[l]), ++l;
      Ans = 0;
      last_block = pos[Q[i].l];
    }

    // 扩展右端点
    while (r < Q[i].r) ++r, Add(x[r], Ans);
    __l = l;
    tmp = Ans;

    // 扩展左端点
    while (__l > Q[i].l) --__l, Add(x[__l], tmp);
    ans[Q[i].id] = tmp;

    // 回滚
    while (__l < l) Del(x[__l]), ++__l;
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}

### 整体二分

#include <bits/stdc++.h>
using namespace std;
const int N = 200020;
const int INF = 1e9;
int n, m;
int ans[N];
// BIT begin
int t[N];
int a[N];
int sum(int p) {
  int ans = 0;
  while (p) {
    ans += t[p];
    p -= p & (-p);
  }
  return ans;
}
void add(int p, int x) {
  while (p <= n) {
    t[p] += x;
    p += p & (-p);
  }
}
// BIT end
int tot = 0;
struct Query {
  int l, r, k, id, type;  // set values to -1 when they are not used!
} q[N * 2], q1[N * 2], q2[N * 2];
void solve(int l, int r, int ql, int qr) {
  if (ql > qr) return;
  if (l == r) {
    for (int i = ql; i <= qr; i++)
      if (q[i].type == 2) ans[q[i].id] = l;
    return;
  }
  int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0;
  for (int i = ql; i <= qr; i++) {
    if (q[i].type == 1) {
      if (q[i].l <= mid) {
        add(q[i].id, 1);
        q1[++cnt1] = q[i];
      } else
        q2[++cnt2] = q[i];
    } else {
      int x = sum(q[i].r) - sum(q[i].l - 1);
      if (q[i].k <= x)
        q1[++cnt1] = q[i];
      else {
        q[i].k -= x;
        q2[++cnt2] = q[i];
      }
    }
  }
  // rollback changes
  for (int i = 1; i <= cnt1; i++)
    if (q1[i].type == 1) add(q1[i].id, -1);
  // move them to the main array
  for (int i = 1; i <= cnt1; i++) q[i + ql - 1] = q1[i];
  for (int i = 1; i <= cnt2; i++) q[i + cnt1 + ql - 1] = q2[i];
  solve(l, mid, ql, cnt1 + ql - 1);
  solve(mid + 1, r, cnt1 + ql, qr);
}
pair<int, int> b[N];
int toRaw[N];
int main() {
  scanf("%d%d", &n, &m);
  // read and discrete input data
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    b[i].first = x;
    b[i].second = i;
  }
  sort(b + 1, b + n + 1);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (b[i].first != b[i - 1].first) cnt++;
    a[b[i].second] = cnt;
    toRaw[cnt] = b[i].first;
  }
  for (int i = 1; i <= n; i++) {
    q[++tot] = {a[i], -1, -1, i, 1};
  }
  for (int i = 1; i <= m; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    q[++tot] = {l, r, k, i, 2};
  }
  solve(0, cnt + 1, 1, tot);
  for (int i = 1; i <= m; i++) printf("%d\n", toRaw[ans[i]]);
}

## 矩阵

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = (int)1e9 + 7;
struct matrix
{
    const static int N = 101;
    int e[N][N], n, m;
    matrix() {}
    matrix(int _n, int _m) : n(_n), m(_m)
    {
        for (int i = 0; i < n; i++)
            memset(e[i], 0, sizeof(int) * N);
    }
    matrix operator*(const matrix &rhs)
    {
        matrix ret(n, rhs.m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < rhs.m; j++)
                for (int z = 0; z < m; z++)
                    ret.e[i][j] = (ret.e[i][j] + 1ll * e[i][z] * rhs.e[z][j]) % mod;
        return ret;
    }
    matrix operator+(const matrix &rhs)
    {
        matrix ret(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                ret.e[i][j] = (e[i][j] + rhs.e[i][j]) % mod;
        return ret;
    }
    matrix operator-(const matrix &rhs)
    {
        matrix ret(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                ret.e[i][j] = (e[i][j] - rhs.e[i][j] + mod) % mod;
        return ret;
    }
    matrix qpow(ll b)
    {
        matrix a = (*this), ret(n, n);
        for (int i = 0; i < n; i++)
            ret.e[i][i] = 1;
        while (b)
        {
            if (b & 1)
                ret = ret * a;
            a = a * a;
            b >>= 1;
        }
        return ret;
    }
};   

## 公式&定理