ACM模板

tarjan

void tarjan(int u){
 // dfn 节点的时间戳 ， low 当前强联通分量根节点的时间戳 ， ssc[i] ， 当前是第i个强连通分量
  // sc 强连通分量的个数 ， sz[i] 强连通分量的大小
   low[u] = dfn[u] = ++dfncnt, s[++tp] = u;
   for (auto x : v[u] {
       if (!dfn[x])
           tarjan(x), low[u] = min(low[u], low[x]);
       else if (!scc[x])
           low[u] = min(low[u], dfn[x]);
   }
   if (dfn[u] == low[u]) {
       ++sc;
       while (s[tp] != u) scc[s[tp]] = sc, sz[sc]++, --tp;
       scc[s[tp]] = sc, sz[sc]++, --tp;
   }
}

tarjan 点双连通分量

int dfn[N] , low[N] , ans[N] , cnt = 0 ;
vector v[N] ;
// ans[] 点所在几个点双连通分量
void tarjan(int u , int f) {
  low[u] = dfn[u] = ++ cnt ;
  ans[u] = 0 ;
  if(f) ans[u] ++ ;
  for(auto x : v[u]) {
    if(x == f) continue ;
    if(!dfn[x]) {
      tarjan(x , u) ;
      low[u] = min(low[u] , low[x]) ;
      if(low[x] < dfn[u]) ans[u] -- ;
      ans[u] ++ ;
    }else low[u] = min(low[u] , dfn[x]) ;
  }
}
int work(){
  for(int i = 1; i <= n ;i ++ ) if(!dfn[i]) tarjan(i , 0) , res ++ ;
}

tarjan边双连通分量

const int N = 5010;//点数
const int M = 20010;//边数，因为是无向图，所以这个值要 *2
struct Edge{
    int to,nxt;
    bool cut;//是否是桥标记
} edge[M];
int head[N],tot , low[N],dfn[N],sta[N],belong[N];//Belong 数组的值是1~block
int id,top , block;//边双连通块数
bool insta[N];
int bridge;//桥的数目
void add(int u,int v){
    edge[tot].to = v;
    edge[tot].nxt = head[u];
    edge[tot].cut=false;
    head[u] = tot++;
}
void Tarjan(int u,int pre){
    int v;
    low[u] = dfn[u] = ++id;
    sta[top++] = u;
    insta[u] = true;
    int pre_cnt = 0;
    for(int i = head[u]; i != -1; i = edge[i].nxt){
        v = edge[i].to;
        if(v == pre && pre_cnt == 0){
            pre_cnt++;
            continue;
        }
        if(!dfn[v]){
            Tarjan(v,u);
            if(low[u]>low[v]) low[u] = low[v];
            if(low[v]>dfn[u]) {
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
        }
        else if( insta[v] && low[u] > dfn[v] )  low[u] = dfn[v];
    }
    if(low[u] == dfn[u]){
        block++;
        do{
            v = sta[--top];
            insta[v] = false;
            belong[v] = block;
        }while( v!=u );
    }
}
void init(){
    tot = 0;
    memset(head,-1,sizeof(head));
}
int du[N];//缩点后形成树，每个点的度数
void solve(int n){
    memset(dfn,0,sizeof(dfn));
    memset(insta,false,sizeof(insta));
    id = top = block = 0;
    Tarjan(1,0);
    int ans = 0;
    memset(du,0,sizeof(du));
    for(int i = 1; i <= n; i++) for(int j = head[i]; j != -1; j = edge[j].nxt) if(edge[j].cut) du[belong[i]]++;
    for(int i = 1; i <= block; i++) if(du[i]==1) ans++; //找叶子结点的个数 ans, 构造边双连通图需要加边(ans+1)/2
    printf("%d\n",(ans+1)/2);
}
int main(){
    int n,m;
    int u,v;
    while(scanf("%d%d",&n,&m)==2){
        init();
        while(m--){
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        solve(n);
    }
    return 0;
}

割点与桥

void Tarjan(int i,int Father){
    father[i]=Father;/*记录每一个点的父亲*/
    dfn[i]=low[i]=tim++;
    for(int j=0;j=2,就是割点*/
        else{
            if(low[i]>=dfn[v])/*割点的条件*/
            is_cut[v]=true;
        }
    }
    if(rootson>1) is_cut[1]=true;
    for(int i=1;i<=n;++i)
         if(is_cut[i]) printf("%d\n",i);
    for(int i=1;i<=n;++i){
        int v =father[i];
        if(v>0&&low[i]>dfn[v])/*桥的条件*/
        printf("%d,%d\n",v,i);
    }
}
int main(){
    input();
    memset(dfn,-1,sizeof(dfn));
    memset(father,0,sizeof(father));
    memset(low,-1,sizeof(low));
    memset(is_cut,false,sizeof(is_cut));
    count();
    return 0;
}

点分治

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 

网络流

最大流最小费用

const int N = 5e4 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int e[N] , ne[N] ;
int h[N] , n , m , s , t , idx ;
ll incf[N] , dis[N] , f[N] , w[N] ;
// incf 是总流量，dis总花费，f边的流量，w边的花费
int vis[N] , pre[N] ;
void add(int a , int b , ll incf , ll dis) {
   e[idx] = b , ne[idx] = h[a] , w[idx] = dis , f[idx] = incf , h[a] = idx ++ ; 
}
void add_edge(int a , int b , ll incf , ll dis) {
   add(a , b , incf , dis) ;
   add(b , a , 0 , -dis) ;
}
bool spfa(int s , int t) {

   memset(incf , 0 , sizeof incf) ;
   memset(dis,  0x3f , sizeof dis) ;
   memset(vis , 0 , sizeof vis) ;
   queue q ;
   q.push(s) ;
   dis[s] = 0 , vis[s] = 1 ;
   incf[s] = INF ;
   while(q.size()) {
   	int u = q.front() ;
   	q.pop() ;
   	vis[u] = 0 ;
   	for(int i = h[u] ; ~i ; i = ne[i]) {
   		int v = e[i] ;
   		if(!f[i]) continue ;
   		if(dis[v] > dis[u] + w[i]) {
   			dis[v] = dis[u] + w[i] ;
   			pre[v] = i ;
   			incf[v] = min(incf[u] , f[i]) ;
   			if(!vis[v]) vis[v] = 1 , q.push(v) ;
			}
   	}
   }
   return incf[t] != 0 ;
}
ll mincost , minflow ;
void MCMF() {
   while(spfa(s , t)) {
   	mincost += 1ll * incf[t] * dis[t] ;
   	minflow += 1ll * incf[t] ;
   	int i = t ;
   	while(i != s) {
   		f[pre[i]] -= incf[t] ;
   		f[pre[i] ^ 1] += incf[t] ;
   		i = e[pre[i] ^ 1] ;
   	}
   }
}
int a[N] ;
int work()
{

 s = 0 , t = n + 1 ;  idx = 0 ;
 memset(h , -1 , sizeof h) ;
 add_edge(s , i , a[i] , 0) 
 // a -> b 流量 花费
 add_edge(a , b , INF , c) ;
 add_edge(b , a , INF , c) ;

 minflow = mincost = 0 ;
 MCMF() ;
 cout << minflow << " " << mincost << "\n" ;
 return 0 ;
}
int main()
{
 //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
 //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
 int n ;
 cin >> n ;
 while(n -- )
 work() ;
 return 0 ;
}
/*

*/
   

Dinic最大流

struct node{
   int u, v, c, next;
}Node[2*N];
void add_(int u, int v, int c){
   Node[cnt].u = u;
   Node[cnt].v = v;
   Node[cnt].c = c;
   Node[cnt].next = head[u];
   head[u] = cnt++;
}
void add(int u, int v, int c){
   add_(u, v, c);
   add_(v, u, 0);
}
bool bfs(){
   queue Q;
   memset(d , 0 , sizeof d) ;
   Q.push(s);
   d[s] = 1;
   while(!Q.empty()){
       int u = Q.front(); Q.pop();
       for(int i=head[u]; i!=-1; i=Node[i].next){
           node e = Node[i];
           if(!d[e.v] && e.c > 0){
               d[e.v] = d[e.u] + 1;
               Q.push(e.v);
               if(e.v == t) return 1;
           }
       }
   }
   return d[t] != 0;
}
int dfs(int u, int cap){
   int ret = 0, V;
   if(u == t || cap == 0)
       return cap;
   for(int &i=cur[u]; i!=-1; i=Node[i].next) {
       node e = Node[i];
       if(d[e.v] == d[u] +  1 && e.c > 0){
           int V = dfs(e.v, min(cap, e.c));
           Node[i].c -= V;
           Node[i^1].c += V;
           ret += V;
           cap -= V;
           if(cap == 0) break;
       }
   }
   if(cap > 0) d[u] = -1;
   return ret;
}
int dinic(int u){
   int ans = 0;
   while(bfs()) {
       memcpy(cur, head, sizeof(head));
       ans += dfs(u, INF);
   }
   return ans;
}
void init() {
 memset(head ,-1,  sizeof head) ;
 cnt = 0 ;
}

固定流量的最小费用

struct edge {
   int to, next, cap;
   ll cos;
}e[M<<1];
struct node {
   ll a, b, c;
}p[55];
vector a[55], b;
int n, m, cnt, s, t, k;
void add(int u, int v, int cap, ll cos) {
   e[cnt].to = v;
   e[cnt].cap = cap;
   e[cnt].cos = cos;
   e[cnt].next = h[u];
   h[u] = cnt++;
   e[cnt].to = u;
   e[cnt].cap = 0;
   e[cnt].cos = -cos;
   e[cnt].next = h[v];
   h[v] = cnt++;
}
bool spfa() {
   queue q;
   memset(pre, -1, sizeof pre);
   memset(vis, 0, sizeof vis);
   memset(dis, 0x3f, sizeof dis);
   dis[s] = 0;
   vis[s] = 1;
   flow[s] = INF;
   q.push(s);
   while (q.size()) {
   	int u = q.front();
   	q.pop();
   	vis[u] = 0;
   	for (int i = h[u]; ~i; i = e[i].next) {
   		int v = e[i].to;
   		if (e[i].cap && dis[v] > dis[u] + e[i].cos) {
   			pre[v] = u;
   			last[v] = i;
   			dis[v] = dis[u] + e[i].cos;
   			flow[v] = min(flow[u], e[i].cap);
   			if (!vis[v]) {
   				q.push(v);
   				vis[v] = 1;
   			}
   		}
   	}
   }
   return pre[t] != -1;
}
void MCMF() {
   while (spfa()) {
   	ans[++k] = ans[k-1] + 1ll*flow[t] * dis[t];
   	int now = t;
   	while (now != s) {
   		e[last[now]].cap -= flow[t];
   		e[last[now] ^ 1].cap += flow[t];
   		now = pre[now];
   	}
   }
}
void solve() {
   scanf("%d %d", &n, &m);
   memset(h, -1, sizeof h);
   memset(ans, 0, sizeof ans);
   cnt = 0;
   k = 0;
// 起点，会点
   s = 0, t = N-2;
   for (int i = 1; i <= b.size(); i++) {//所有机器向汇点连边
   	add(i + n, t, 1, 0);
   }
   MCMF();
   // 固定流量的最小费用
   for (int i = 1; i <= k; i++) {
   	if (i != k) printf("%lld ", ans[i]);
   	else printf("%lld\n", ans[i]);
   }
}

字符串

后缀数组

int y[N], x[N], c[N], sa[N], rk[N], height[N] , st[30][N] ;
int get_SA() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
        for (int i = 1; i <= m; ++i) c[i] = 0;
        for (int i = 1; i <= n; ++i) ++c[x[i]];
        for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
        for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1;
        num = 1;
        for (int i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if (num == n) break;
        m = num;

    }
    return 0;
}
int get_height() {
    int k = 0;
    for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
    for (int i = 1; i <= n; ++i) {
        if (rk[i] == 1) continue;
        if (k) --k;
        int j = sa[rk[i] - 1];
        while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
        height[rk[i]] = k;
    }
    return 0 ;
}
void build_st() {
    for (int i = 1; i <= n; i++) st[0][i] = height[i];
    for (int k = 1; k <= 19; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
        }
    }
    return ;
}
int lcp(int x, int y) {
    int l = rk[x], r = rk[y];
    if (l > r) swap(l, r);
    if (l == r) return n - x + 1;
    int t = log2(r - l);
    return min(st[t][l + 1], st[t][r - (1 << t) + 1]);
}
struct node {
  int l , r , sum ;
}t[N * 4];
int tot = 0 ;
void up(int now) {
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
void build(int &now , int l , int r) {
  t[now = ++ tot].sum = 0 ;
  if(l == r) return ;
  int mid = l + r >> 1 ;
  build(t[now].l , l , mid) ;
  build(t[now].r , mid + 1 , r) ;
  return ;
}
void update(int &now , int last , int l , int r , int pos) {
  t[now = ++ tot] = t[last] ;
  t[now].sum ++ ;
  if(l == r) return ;
  int mid = l + r >> 1 ;
  if(pos <= mid) update(t[now].l , t[last].l , l , mid , pos) ;
  else update(t[now].r , t[last].r , mid + 1 , r , pos) ;
  return ;
}
int ask(int now , int last , int l , int r , int k) {
  if(l == r) return l ;
  int sum = t[t[now].l].sum - t[t[last].l].sum ;
  int mid = l + r>> 1 ;
  if(sum >= k) return ask(t[now].l , t[last].l , l , mid , k) ;
  else return ask(t[now].r , t[last].r , mid + 1 , r , k - sum) ;
}
int root[N] ;
int work(){
  int q ;
  tot = 0 ;
  scanf("%d%d" , &n , &q) ;
  scanf("%s" , s + 1) ;
  m = 123 ;
  get_SA() ;
  get_height() ;
  build_st() ;
  build(root[0] , 1,  n ) ;
  for(int i = 1; i <= n; i ++ ) update(root[i] , root[i - 1] , 1 , n , sa[i]) ;
  while(q --) {
    int l , r , k ;
    scanf("%d%d%d" , &l , &r , &k) ;
    int len = r - l + 1 ;
    int left = 1 , right = rk[l] ;
    int ans = rk[l] ;
    while(left <= right) {
      int mid = left + right >> 1 ;
      if(lcp(sa[mid] , l) >= len) right = mid - 1 , ans = mid ;
      else left = mid + 1 ;
    }
    int LL = ans ;
    ans = rk[l] ;
    right = n ;
    left = rk[l] ;
    while(left <= right) {
      int mid = left + right >> 1 ;
      if(lcp(sa[mid] , l) >= len) left = mid + 1 , ans = mid ;
      else right = mid - 1 ;
    }
    int RR = ans ;
    if(RR - LL + 1 < k) puts("-1") ;
    else printf("%d\n" , ask(root[RR] , root[LL - 1] , 1 , n , k)) ;
  }
  return 0 ;
}

AC自动机

struct Trie{
 int t[N][26] , fail[N] , cnt[N] , in[N] , q[N] , h , tail , tot ;
 void init() {
   tot = 0 ;
   memset(fail , 0 , sizeof fail) ;
   memset(t , 0 , sizeof t) ;
   memset(cnt , 0 , sizeof cnt) ;
   memset(q , 0 , sizeof q) ;
 }
 int ins(char *x) {
   int i = 0 ;
   for(int j = 0 ;x[j] ;j ++ ) {
     int c = x[j] - 'a' ;
     if(!t[i][c]) t[i][c] = ++ tot ;
     i = t[i][c] ;
   }
   return i ;
 }
 void get_fail() {
   h = 1 ,tail = 0 ;
   for(int i = 0 ;i < 26 ;i ++ ) if(t[0][i]) q[++ tail] = t[0][i] ;
   while(h <= tail) {
     int i = q[h ++] ;
     for(int j = 0 ;j < 26 ;j ++ ) {
       if(t[i][j]) {
         fail[t[i][j]] = t[fail[i]][j] ;
         q[++ tail] = t[i][j] ;
       }else {
         t[i][j] = t[fail[i]][j] ;
       }
     }
   }
 }
 void solve() {
   for(int i = tail ;i > 0 ;i --) cnt[fail[q[i]]] += cnt[q[i]] ;
 }
}T;
char x[510][510] ;
char s[N] ;
int id[N] ;
int work()
{
 int n , m , q ;
 scanf("%d" , &n) ;
 T.init() ;
 for(int i = 1; i <= n; i ++ ) {
   scanf("%s" , s) ;
   id[i] = T.ins(s) ;
 }
 T.get_fail() ;
 scanf("%s" , s) ;
 int p = 0 ;
 for(auto x : s)
  p = T.t[p][x - 'a'] , T.cnt[p] ++ ;
 T.solve() ;
 int ans = 0 ;
 for(int i = 1; i <= n ;i ++ )
   ans += T.cnt[id[i]] ;
 cout << ans << endl ;
 return 0 ;
}

字符串最小表示法

int getmin(int *a){
   static int b[12] ;
   for(int i = 0 ;i < 12 ;i ++) b[i] = a[i % 6] ;
   int i = 0 , j = 1 , k ;
   while(i < 6 && j < 6){
        for(k = 0 ;k < 6 && b[j + k] == b[i + k] ; k ++)  ;
        if(k == 6) break ;
        if(b[i + k] > b[j + k]){
              i += k + 1 ;
              if(i == j) i ++ ;
          }
        if(b[i + k] < b[j + k]){
             j += k + 1 ;
             if(i == j) j ++ ;
         }
    }
    k = min(i , j) ;
    for(int i = 0 ; i < 6 ;i ++)
     a[i] = b[i + k] ;
    return 0 ;
}

马拉车算法

void init(int l , int r){
   int k=0;
   str[k++] = '$';
   for(int i=l;i<=r;i++){
       str[k++]='#';
       str[k++]=s[i];
   }
   str[k++]='#';
   len=k;
   str[k] = '\0' ;
}
int ans = 0 , flag ;
int Manacher(){
 Len[0] = 0;
 int sum = 0;
 mx = 0;
 id = 0 ;
 // cout << str << endl ;
 for(int i=1;i mx){        // 更新最长的回文串
     mx = Len[i] + i;          // mx是回文串右边一个位置
     id = i;             //id是回文串的中心
     sum = Max(sum, Len[i]);         // sum 是回文串的长度 + 1

   }
   // cout << i << " " << Len[i] << endl ;
   // if(Len[i] == i)  表示前缀是回文的
   //  {
   //    if(ans < Len[i])
   //     ans = Len[i] - 1 , flag = 1 ;
   //  }
   // if(Len[i] + i == len)  表示后缀是回文的
   //  if(ans < Len[i])
   //   ans = Len[i] - 1 , flag = 2 ;
 }
 return sum - 1 ;
}

kmp

void get_next()
{
   for(int i = 2, j = 0 ;i <= n;i ++)
   {
       while(j && p[i] != p[j + 1]) j = nextp[j];
       if(p[i] == p[j + 1]) j ++ ;
       nextp[i] = j ;
   }
}
int main()
{
 // 在s串里面查找
   cin >> s + 1 ;
   m = strlen(s + 1);
   cin >> p + 1 ;
   n = strlen(p + 1) ;
   get_next();
   int x = 0 ;
   for(int i = 1 , j = 0;i <= m;i ++){
       while(j && s[i] != p[j + 1]) j = nextp[j] ;
       if(s[i] == p[j + 1]) j ++ ;
       if(j == n){
         //  cout << i - n << " " ;
           x ++ ;
           j = nextp[j] ;
       }
   }
   cout << x << endl  ;
   return 0;
}

数据结构

字典树

区间内小于某个数的所有数之和

int n , m , root[N * 20] ;
ll a[N] , bin[N] ;
struct node {
 ll sum , l , r ;
}t[N * 40];
void fj(ll x) {
 if(x > 1000000000ll) x = 1000000001ll ;
 for(int i = 0 ;i <= 30 ;i ++ )
  bin[i] = (x >> i) & 1ll ;
}
int tot = 0 ;
void insert(int &now , int last , int id , ll w) {
 t[now = ++ tot] = t[last] ;
 if(id < 0) {
   t[now].sum += w ;
   return ;
 }
 if(!bin[id]) insert(t[now].l , t[last].l , id - 1 , w) ;
 else insert(t[now].r , t[last].r , id - 1 , w) ;
 t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
// 贪心的走
ll ask(int rt , int id) {
 if(id < 0 || !rt) return t[rt].sum ;
 ll res = 0 ;
 if(!bin[id]) res = ask(t[rt].l , id - 1) ;
 else res = t[t[rt].l].sum + ask(t[rt].r , id - 1) ;
 return res ;
}
int work()
{
 scanf("%d%d" , &n , &m) ;
 for(int i = 1; i <= n ;i ++ ) {
   scanf("%d" , &a[i]) ;
   fj(a[i]) ;
   insert(root[i] , root[i - 1] , 30 , a[i]) ;
 }
 for(int i = 1; i <= m ;i ++ ) {
   int l , r ;
   scanf("%d%d" , &l , &r) ;
   ll sum = 1 , last = 0 ;
   while(1) {
     fj(sum) ;
     ll temp = ask(root[r] , 30) - ask(root[l - 1] , 30) ;
     if(temp == last) {
       printf("%lld\n" , sum) ;
       break ;
     }
     last = temp , sum = temp + 1 ;
   }
 }
 return 0 ;
}

主席树

主席树求区间小于某个数的个数

int root[N] , tot ;
struct node {
int l , r , sum ;
}t[N];
void build(int &now , int l , int r) {
t[now = ++ tot].sum = 0 ;
if(l == r) return ;
int mid = l + r >> 1 ;
build(t[now].l , l , mid) ;
build(t[now].r , mid + 1 , r) ;
return ;
}
void up(int now) {
t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
void update(int &now , int last , int l , int r , int pos) {
t[now = ++ tot] = t[last] ;
if(l == r) {
  t[now].sum ++ ;
  return ;
}
int mid = l + r >> 1 ;
if(pos <= mid) update(t[now].l , t[last].l , l , mid , pos) ;
else update(t[now].r , t[last].r , mid + 1 , r , pos) ;
up(now) ;
return ;
}
int ask(int now , int last , int l , int r , int k) {
if(!k) return 0 ;
if(r <= k) return  t[now].sum - t[last].sum ;
int mid = l + r >> 1 ;
int ans = 0 ;
if(k <= mid) ans += ask(t[now].l , t[last].l , l , mid , k) ;
else ans += ask(t[now].l , t[last].l , l , mid , k) + ask(t[now].r , t[last].r , mid + 1 , r , k ) ;
return ans ;
}
int ca = 0 ;
int work()
{
int n , m ;
scanf("%d%d" , &n , &m) ;
for(int i = 1; i <= n ;i ++ ) scanf("%d" , &a[i]) , b[i] = a[i] ;
sort(b + 1 , b + n + 1) ;
cnt = unique(b + 1,  b + n + 1) - b - 1 ;
for(int i = 1; i <= n ;i ++ ) a[i] = lower_bound(b + 1 , b + cnt + 1 , a[i]) - b ;
tot = 0 ;
build(root[0] , 1 , cnt) ;
for(int i = 1 ; i <= n ;i ++ )
  update(root[i] , root[i - 1] , 1 , cnt , a[i]) ;
printf("Case #%d:\n" , ++ ca) ;
for(int i = 1; i <= m ;i ++ ) {
  int l , r , x , y ;
  scanf("%d%d%d%d" , &l , &r , &x , &y) ;
  y = upper_bound(b + 1 , b + cnt + 1 , y) - b - 1 ;
  x = upper_bound(b + 1 , b + cnt + 1 , x - 1) - b - 1;
  printf("%d\n" , ask(root[r] , root[l - 1] , 1 , cnt , y) - ask(root[r] , root[l - 1] , 1 , cnt , x)) ;
}
return 0 ;
}

主席树求区间第k小(静态)

struct Tree {
  int l, r, sum;
} T[MAXN * 40];
vector v ;
int cnt, root[MAXN], a[MAXN];
void Init() 
{
  cnt = 0;
  T[cnt].l = 0;
  T[cnt].r = 0;
  T[cnt].sum = 0;
  root[cnt] = 0;
  v.clear();
}
int getid(int x) 
{ 
   return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; 
}
void Update(int l, int r, int &x, int y, int pos) 
{
  T[++cnt] = T[y], T[cnt].sum++, x = cnt;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (mid >= pos)
      Update(l, mid, T[x].l, T[y].l, pos);
  else
      Update(mid + 1, r, T[x].r, T[y].r, pos);
}
int Query(int l, int r, int x, int y, int k) 
{
  if (l == r) return l;
  int mid = (l + r) >> 1;
  int sum = T[T[y].l].sum - T[T[x].l].sum;
  if (sum >= k)
      return Query(l, mid, T[x].l, T[y].l, k);
  else
      return Query(mid + 1, r, T[x].r, T[y].r, k - sum);
}
int main() 
{
  Init();
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) 
      scanf("%d", &a[i]),v.push_back(a[i]);
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; i++)
      Update(1, n, root[i], root[i - 1], getid(a[i]));
  int l, r, k;
  for (int i = 1; i <= m; i++) 
  {
      scanf("%d%d%d", &l, &r, &k);
      printf("%d\n", v[Query(1, n, root[l - 1], root[r], k) - 1]);
  }
  return 0;
}

主席树求区间小于某个数所有数的和

struct node {
ll sum ;
int l , r ;
}t[N * 40];
void fj(ll x) {
if(x > 1000000000ll) x = 1000000001ll ;
for(int i = 0 ;i <= 30 ;i ++ )
 bin[i] = (x >> i) & 1ll ;
}
int tot = 0 ;
void insert(int &now , int last , int id , ll w) {
t[now = ++ tot] = t[last] ;
if(id < 0) {
  t[now].sum += w ;
  return ;
}
if(!bin[id]) insert(t[now].l , t[last].l , id - 1 , w) ;
else insert(t[now].r , t[last].r , id - 1 , w) ;
t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
// 贪心的走
ll ask(int rt , int id) {
if(id < 0 || !rt) return t[rt].sum ;
ll res = 0 ;
if(!bin[id]) res = ask(t[rt].l , id - 1) ;
else res = t[t[rt].l].sum + ask(t[rt].r , id - 1) ;
return res ;
}
int work()
{
scanf("%d%d" , &n , &m) ;
for(int i = 1; i <= n ;i ++ ) {
  scanf("%d" , &a[i]) ;
  fj(a[i]) ;
  insert(root[i] , root[i - 1] , 30 , a[i]) ;
}
for(int i = 1; i <= m ;i ++ ) {
  int l , r ;
  scanf("%d%d" , &l , &r) ;
  ll sum = 1 , last = 0 ;
  while(1) {
    fj(sum) ;
    ll temp = ask(root[r] , 30) - ask(root[l - 1] , 30) ;
    if(temp == last) {
      printf("%lld\n" , sum) ;
      break ;
    }
    last = temp , sum = temp + 1 ;
  }
}
return 0 ;
}

待修主席树(树状数组套主席树)

const int N = 200000 + 5;
int n, m, L[30][30], R[30][30], cl, cr;
inline int lowbit(int x){return x & -x;}
struct SEG{
    struct node{
        int ls,rs;
        int sum;
    }t[N*200];
    int rt[N], tot, maxn, res;
    void update(int &rt, int l, int r, int pos, int val){
        if(!rt) rt = ++tot;
        t[rt].sum += val;
        if(l == r)return;
        int mid = l + r >> 1;
        if(pos <= mid) update(t[rt].ls, l, mid, pos, val);
        else update(t[rt].rs, mid+1, r, pos, val);
    }
    void update(int x, int pos, int v){ // [1 , x] update pos += v 
        for(;x<=maxn;x+=lowbit(x))update(rt[x],1,n,pos,v);
    }
    void query(int dep, int l, int r, int ql, int qr){ // [l , r] find [ql , qr] ' s number
        if(ql > qr) return;
        if(l >= ql && r <= qr){
            for(int i=1;i<=cl;i++) res -= t[L[dep][i]].sum;
            for(int i=1;i<=cr;i++) res += t[R[dep][i]].sum;
            return;
        }
        int mid = l+r>>1;
        if(ql <= mid){
            for(int i=1;i<=cl;i++)L[dep+1][i] = t[L[dep][i]].ls;
            for(int j=1;j<=cr;j++)R[dep+1][j] = t[R[dep][j]].ls;
            query(dep+1,l,mid,ql,qr);
        }
        if(qr > mid){
            for(int i=1;i<=cl;i++)L[dep+1][i] = t[L[dep][i]].rs;
            for(int j=1;j<=cr;j++)R[dep+1][j] = t[R[dep][j]].rs;
            query(dep+1,mid+1,r,ql,qr);
        }
    }
}seg;
int main() {
            // 在区间[1 , x] 里面插入pos 位置上面 val值
            seg.update(x , pos , val) ;
            cl = cr = 0;
            // 查询区间[x , y]里面[l , r]位置 的个数
            for(int j=x;j;j-=lowbit(j))L[0][++cl] = seg.rt[j];
            for(int j=y;j;j-=lowbit(j))R[0][++cr] = seg.rt[j];
            seg.res = 0;
            seg.query(0, 1, n, l, r);
            printf("%d\n",seg.res);
    return 0;
}

虚树

void dfs(int u){
   dfn[u] = ++idx;
   deep[u] = deep[fa[u][0]] + 1;
   for(int e : RG[u]){
       int v = U[e] ^ V[e] ^ u;
       if(v == fa[u][0]) continue;
       me[v] = C[e];
       if(u != 1 && me[u] < me[v]) me[v] = me[u];
       fa[v][0] = u;
       dfs(v);
   }
}
int LCA(int u,int v){
   if(deep[u] < deep[v]) swap(u,v);
   int delta = deep[u] - deep[v];
   for(int i = 19;i >= 0;--i){
       if((delta >> i) & 1) u = fa[u][i];
   }
   for(int i = 19;i >= 0;--i){
       if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
   }
   if(u == v) return u;
   return fa[u][0];
}
bool comp(int a,int b){
   return dfn[a] < dfn[b];
}
void insert(int u){
   if(top == 1) {stk[++top] = u;return;}
   int lca = LCA(u,stk[top]);
   if(lca == stk[top]) {stk[++top] = u;return ;}
   while(top > 1 && dfn[lca] <= dfn[stk[top-1]]){
       VG[stk[top-1]].push_back(stk[top]);
       --top;
   }
   if(lca != stk[top]) {
       VG[lca].push_back(stk[top]);
       stk[top] = lca;
   }
   stk[++top] = u;
}
int idq[maxn],mark[maxn];
ll DP(int u){
   ll cost = 0;
   for(int v : VG[u])
       cost += min(me[v],DP(v));
   VG[u].clear();
   if(mark[u]) return me[u];
   else return cost;
}
int main(){
   init();
   ios::sync_with_stdio(false);
   cin >> n;
   for(int i = 1;i < n;++i){
       cin >> U[i] >> V[i] >> C[i];
       RG[U[i]].push_back(i);
       RG[V[i]].push_back(i);
   }
   dfs(1);
   for(int t = 1;t <= 19;++t) for(int i = 1;i <= n;++i){
       fa[i][t] = fa[fa[i][t-1]][t-1];
   }
   cin >> m;
   for(int i = 0;i < m;++i){
       int sz;
       cin >> sz;
       for(int j = 0;j < sz;++j){
           cin >> idq[j];
           mark[idq[j]] = 1;
       }
       sort(idq,idq+sz,comp);
       top = 0;
       stk[++top] = 1;
       for(int j = 0;j < sz;++j) insert(idq[j]);
       while(top > 0) {
           VG[stk[top-1]].push_back(stk[top]);
           top--;
       }
       cout << DP(1) << endl;
       for(int j = 0;j < sz;++j) VG[idq[j]].clear(),mark[idq[j]] = 0;
       VG[0].clear();
   }
   return 0;
}

线段树

线段树板子乘加

//线段树操作   区间最大值  单点修改  单点查询
//             区间修改  区间查询   最大连续和

#include 
using namespace std;
const int N = 1e5 + 10 ;
typedef long long ll;
int a[N];
struct node{
  ll muti , add , v;
}tree[4 * N];
int n , m , mod;
void pushdown(int root ,int l,int r){
  int mid = l + r >> 1;
  tree[root * 2].v =(tree[root * 2].v * tree[root].muti + tree[root].add * (mid - l + 1)) % mod;
  tree[root * 2 + 1].v =(tree[root * 2 + 1].v * tree[root].muti + tree[root ].add * (r - mid)) % mod;
  tree[root * 2].muti =(tree[root * 2].muti * tree[root].muti) % mod ;
  tree[root * 2 + 1].muti =(tree[root * 2 + 1].muti * tree[root].muti) % mod ;
  tree[root * 2].add =(tree[root * 2].add * tree[root].muti + tree[root].add) % mod ;
  tree[root * 2 + 1].add =(tree[root * 2 + 1].add * tree[root].muti + tree[root].add) % mod ;
  tree[root].muti = 1 ,tree[root].add = 0;
  return ;
}
void build(int root ,int l,int r){
  tree[root].add = 0,tree[root].muti = 1;
  if(l == r){
  	tree[root].v = a[l] ; return ;
  }
  int mid  = l + r >> 1 ;
  build(root * 2 , l, mid) ,build(root * 2 + 1,mid + 1 ,r );
  tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v ) % mod;
  return ;

}
void change1(int root ,int treel,int treer ,int x, ll k){//单点修改   将第x 个修改为 k
  tree[root].v += k;
  int mid = treel + treer >> 1;
  if(x > mid) change1(root * 2 + 1,mid + 1,treer , x , k);
  else change1(root * 2 , treel,mid , x , k);
  tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v) % mod ;
  return ;
}
int query1(int root,int treel,int treer,int x){ // 单点查询   第x个点
  if(treel == treer) return tree[root].v ;
  int mid = treel + treer >> 1;
  if(x <= mid) query1(root * 2 , treel ,mid ,x);
  else query1(root * 2 + 1 ,mid + 1 ,treer ,x) ;
}
void change2(int root,int treel,int treer,int l,int r,ll k){ // 区间修改   乘法   x - y区间乘上 k
  if(l >treer || r < treel) return ;
  if(l <= treel && treer <= r){
  	tree[root].v =(tree[root].v * k) % mod ;
  	tree[root].muti = (tree[root].muti * k) % mod ;
  	tree[root].add = (tree[root].add * k) % mod ;
  	return ;
  }
  pushdown(root,treel,treer);
  int mid = treel + treer >> 1 ;
  change2(root * 2,treel,mid , l ,r ,k);
  change2(root * 2 + 1,mid + 1,treer, l ,r ,k);
  tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v) % mod ;
  return ;
}
void change3(int root,int treel,int treer,int l,int r,ll k){ // 区间修改  加法  x- y区间加上k
  if(l >treer || r < treel) return ;
  if(l <= treel && treer <= r){
  	tree[root].v =(tree[root].v + k*(treer- treel + 1)) % mod ;
  	tree[root].add = (tree[root].add + k) % mod ;
  	return ;
  }
  pushdown(root,treel,treer);
  int mid = treel + treer >> 1 ;
  change3(root * 2,treel,mid , l ,r ,k);
  change3(root * 2 + 1,mid + 1,treer, l ,r ,k);
  tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v) % mod ;
  return ;
}

ll query2(int root,int treel,int treer,int l,int r){ // 区间求和  求区间x - y 的和
  if(l >treer || r > 1;
  return (query2(root * 2 ,treel,mid , l ,r) + query2(root * 2 + 1,mid + 1,treer ,l,r))%mod ;
}

线段树区间最值

void up(int rt){
minx[rt] = max(minx[ls] , minx[rs]) ;
}
void build(int rt , int l , int r){
if(l == r) {
  minx[rt] = a[l] ;
  return ;
}
int mid = l + r >> 1 ;
build(ls , l , mid) ;
build(rs , mid + 1 , r) ;
up(rt) ;
return ;
}
void down(int rt , int l , int r){
if(lazy[rt]) {
  lazy[ls] += lazy[rt] ;
  lazy[rs] += lazy[rt] ;
  minx[ls] += lazy[rt] ;
  minx[rs] += lazy[rt] ;
  minx[rt] = max(minx[ls] , minx[rs]) ;
  lazy[rt] = 0 ;
}
return ;
}
void add(int rt , int l , int r , int ql , int qr , ll k){
if(ql <= l && r <= qr) {
  minx[rt] += k ;
  lazy[rt] += k ;
  return ;
}
down(rt , l , r) ;
int mid = l + r >> 1 ;
if(ql <= mid) add(ls , l , mid , ql , qr , k) ;
if(qr > mid) add(rs , mid + 1 , r , ql , qr , k) ;
up(rt) ;
return ;
}
ll ask(int rt , int l , int r , int ql , int qr){
if(ql <= l && r <= qr) return minx[rt] ;
down(rt , l , r) ;
ll ans = 0 ;
int mid = l + r >> 1 ;
if(ql <= mid) ans = max(ans , ask(ls , l , mid , ql , qr)) ;
if(qr > mid) ans = max(ans , ask(rs , mid + 1 , r , ql , qr)) ;
return ans ;
}

线段树维护矩阵乘法

struct node {
ll a[2][2] ;
} ;
char a[N] ;
node muti(node a , node b){
node res ;
for(int i = 0 ;i < 2; i ++ )
 for(int j = 0 ;j < 2 ;j ++ )
  res.a[i][j] = 0 ;
for(int k = 0 ;k < 2; k ++ )
 for(int i = 0 ;i < 2; i ++ )
  for(int j = 0 ;j < 2; j ++ )
    res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j] % mod ) % mod ;
return res ;
}
struct Node {
int l , r , lazy ;
node ans , rans ;
}tr[N];
void up(int rt){
tr[rt].ans = muti(tr[ls].ans , tr[rs].ans) ;
tr[rt].rans = muti(tr[ls].rans , tr[rs].rans) ;
return ;
}
void down(int rt){
if(tr[rt].lazy) {
  swap(tr[ls].ans , tr[ls].rans) ;
  swap(tr[rs].ans , tr[rs].rans) ;
  tr[ls].lazy ^= 1 ;
  tr[rs].lazy ^= 1 ;
  tr[rt].lazy ^= 1 ;
}
return ;
}
void build(int rt , int l , int r){
tr[rt].l = l , tr[rt].r = r ;
tr[rt].lazy = 0 ;
if(l == r) {
  if(a[l] == 'A')  {
    tr[rt].ans.a[0][0] = 1 , tr[rt].ans.a[0][1] = 0 ;
    tr[rt].ans.a[1][0] = 1 , tr[rt].ans.a[1][1] = 1 ;
    tr[rt].rans.a[0][0] = 1 , tr[rt].rans.a[0][1] = 1 ;
    tr[rt].rans.a[1][0] = 0 , tr[rt].rans.a[1][1] = 1 ;
  }else {
    tr[rt].ans.a[0][0] = 1 , tr[rt].ans.a[0][1] = 1 ;
    tr[rt].ans.a[1][0] = 0 , tr[rt].ans.a[1][1] = 1 ;
    tr[rt].rans.a[0][0] = 1 , tr[rt].rans.a[0][1] = 0 ;
    tr[rt].rans.a[1][0] = 1 , tr[rt].rans.a[1][1] = 1 ;
  }
  return ;
}
int mid = l + r >> 1 ;
build(ls , l , mid) ;
build(rs , mid + 1 , r) ;
up(rt) ;
return ;
}
void update(int rt , int l , int r){
if(l <= tr[rt].l && tr[rt].r <= r) {
  tr[rt].lazy ^= 1 ;
  swap(tr[rt].ans , tr[rt].rans) ;
  return ;
}
down(rt) ;
int mid = tr[rt].l + tr[rt].r >> 1 ;
if(l <= mid) update(ls , l , r) ;
if(r > mid) update(rs , l , r) ;
up(rt) ;
return ;
}
node ask(int rt , int l , int r){
if(tr[rt].l >= l && tr[rt].r <= r) return tr[rt].ans ;
down(rt) ;
int mid = tr[rt].l + tr[rt].r >> 1 ;
node ans ;
ans.a[0][0] = 1 , ans.a[0][1] = 0 ;
ans.a[1][0] = 0 , ans.a[1][1] = 1 ;
if(l <= mid) ans = muti(ans , ask(ls , l , r)) ;
if(r > mid) ans = muti(ans , ask(rs , l , r)) ;
up(rt) ;
return ans ;
}

扫描线

const int MAX=20000 ;
int mark[MAX<<2];//记录某个区间的下底边个数
double sum[MAX<<2];//记录某个区间的下底边总长度
double Hash[MAX];//对x进行离散化,否则x为浮点数且很大无法进行线段树
//以横坐标作为线段(区间),对横坐标线段进行扫描
//扫描的作用是每次更新下底边总长度和下底边个数,增加新面积
struct seg{//线段
  double l,r,h;
  int d;
  seg(){}
  seg(double x1,double x2,double H,int c):l(x1),r(x2),h(H),d(c){}
  bool operator<(const seg &a)const{
  	return h>1;
  if(L<=mid)Update(L,R,d,n<<1,left,mid);
  if(R>mid)Update(L,R,d,n<<1|1,mid+1,right);
  Upfather(n,left,right);
}
int search(double key,double* x,int n){
  int left=0,right=n-1;
  while(left<=right){
  	int mid=left+right>>1;
  	if(x[mid] == key)return mid;
  	if(x[mid]>key)right=mid-1;
  	else left=mid+1;
  }
  return -1;
}
int main(){
  int n,num=0;
  double x1,x2,y1,y2;
  while(cin>>n,n){
  	int k=0;
  	for(int i=0;i>x1>>y1>>x2>>y2;
  		Hash[k]=x1;
  		s[k++]=seg(x1,x2,y1,1);
  		Hash[k]=x2;
  		s[k++]=seg(x1,x2,y2,-1);
  	}
  	sort(Hash,Hash+k);
  	sort(s,s+k);
  	int m=1;
  	for(int i=1;i

const int N = 1e6 + 10 , INF = 0x3f3f3f3f , p = 1e9 + 7 , mod = 65536 ;
ll pw[N << 2] , hash1[N << 2] , hash2[N << 2] , sum[N << 2] , PW[N] ;
int a[N] ;
void push_up(int rt) {
 sum[rt] = (sum[ls] + sum[rs]) % mod ;
 hash1[rt] = (hash1[ls] * pw[rs] % p + hash1[rs]) % p ;
 hash2[rt] = (hash2[rs] * pw[ls] % p + hash2[ls]) % p ;
 pw[rt] = pw[ls] * pw[rs] % p ;
 return ;
}
void build(int rt , int l , int r) {
 if(l == r) {
   pw[rt] = 19260817 ;
   hash1[rt] = hash2[rt] = sum[rt] = a[l] ;
   return ;
 }
 int mid = l + r >> 1 ;
 build(ls , l , mid) ;
 build(rs , mid + 1 , r) ;
 push_up(rt) ;
}
void update(int rt , int l , int r , int p) {
 if(l == r) {
   hash1[rt] = hash2[rt] = sum[rt] = a[l] ;
   return  ;
 }
 int mid = l + r >> 1 ;
 if(p <= mid) update(ls,  l , mid , p) ;
 else update(rs , mid + 1 , r , p) ;
 push_up(rt) ;
}
ll ask1(int rt , int l , int r , int ql , int qr) {
 if(ql <= l && r <= qr) return sum[rt] ;
 int mid = l + r >> 1 , ans = 0 ;
 if(ql <= mid) ans = (ans + ask1(ls , l , mid , ql , qr)) % mod ;
 if(qr > mid) ans = (ans + ask1(rs , mid + 1 , r  , ql , qr)) % mod ;
 return ans ;
}
ll ask2(int rt , int l , int r , int ql , int qr) {
 if(ql <= l && r <= qr)
   return hash1[rt] ;
 int mid = l + r >> 1 ;
 ll ans = 0 ;
 if(ql <= mid) ans = (ans + ask2(ls , l , mid , ql , qr) * PW[mid < min(qr , r) ? min(qr , r) - mid : 0]) % p ;
 if(qr > mid) ans = (ans + ask2(rs , mid + 1 , r , ql , qr)) % p ;
 return ans ;
}
ll ask3(int rt , int l , int r , int ql , int qr) {
 if(ql <= l && r <= qr) return hash2[rt] ;
 int mid = l + r >> 1 ;
 ll ans = 0 ;
 if(ql <= mid)  ans = (ans + ask3(ls , l , mid , ql , qr)) % p ;
 if(qr > mid) ans = (ans + ask3(rs , mid + 1 , r , ql , qr) * PW[max(l , ql) <= mid ? mid - max(l , ql) + 1 : 0]) % p ;
 return ans ;
}
// 1 a[l , r] ++
// 2 [x , x + L - 1] == [y , y + L - 1]
int main()
{
 int n , q ;
 memset(pw , 1 , sizeof pw) ;
 scanf("%d%d" , &n , &q) ;
 PW[0] = 1 ;
 for(int i = 1; i <= n ;i ++ )
  PW[i] = PW[i - 1] * 19260817 % p ;
 for(int i = 1; i <= n ;i ++ ) scanf("%d" , &a[i]) ;
 for(int i = n ;i >= 2; i -- ) {
   a[i] -= a[i - 1] ;
   if(a[i] < 0) a[i] += mod ;
 }
 build(1 , 1 , n) ;
 while(q --) {
   int op ;
   scanf("%d" , &op) ;
   if(op == 1) {
     int l , r ;
     scanf("%d%d" , &l , &r) ;
     a[l] = (a[l] + 1) % mod ;
     update(1 , 1 , n , l) ;
     if(r != n) {
       a[r + 1] -- ;
       if(a[r + 1] < 0) a[r + 1] += mod ;
       update(1 , 1 , n , r + 1) ;
     }
   }else {
     int x , y , L ;
     scanf("%d%d%d" , &x , &y , &L) ;
     if(x > y) swap(x , y) ;
     if(x == y) puts("yes") ;
     else if(ask1(1 , 1 , n , x + 1 , y) != 0) puts("no") ;
     else if(ask2(1 , 1 , n , x + 1 , x + L - 1) != ask2(1 , 1 , n , y + 1 , y + L - 1))
               puts("no") ;
     else if(ask3(1 , 1 , n , x + 1 , x + L - 1) != ask3(1 , 1 , n , y + 1 , y + L - 1))
                puts("no") ;
     else puts("yes") ;
    }
 }
 return 0 ;
}

void get(){
 for(int i = 2; i < N ;i ++ ) {
   if(!vis[i]) prime[++ tot] = i ;
   for(int j = 1; j <= tot && i * prime[j] < N ;j ++ ) {
     vis[i * prime[j]] = 1 ;
     if(i % prime[j] == 0) break ;
   }
 }
}
ll f[N] ;
void dfs2(int u , int fa , int rt) {
 sz[u] = 1 , f[u] = 1;
 for(auto x : v[u]) {
   if(x == fa || x == rt) continue ;
   dfs2(x , u , rt) ;
   sz[u] += sz[x] ;
   f[u] += 1ll * prime[sz[x]] * f[x] ;
 }
}

//f[i][i] 存i点的度数
//f[i][j] 存i点到j点的边数的相反数
//ans为图的生成树数量
void add(int u,int v){
   f[u][u]++;f[v][v]++;
   f[u][v]--;f[v][u]--;
}
int u[N] , v[N] , w[N];
ll gauss () {// 生成树的数量
   ll ans = 1 ;
   for (int i = 1; i < n; i ++) {
       for (int j = i + 1; j < n; j ++) {
           while (f[j][i]) {
               ll t = f[i][i] / f[j][i] ;
               for (int k = i; k < n; k ++)
                   f[i][k] = (f[i][k] - t * f[j][k] + mod) % mod ;
               swap(f[i], f[j]) ;
               ans = -ans ;
           }
       }
       ans = (ans * f[i][i]) % mod ;
   }
   return (ans + mod) % mod ;
}

/*
1. CF600E - Lomsat gelral
题意
N个节点以点1为根的树，每一个节点有一个颜色color[i],对于一个以u为根的子树来说，
他的子树中的节点有多种颜色，现在求出出现次数最多的颜色(可能有多个颜色出现次数相同)，并将出现次数求和
输出以所有点的答案
分析
以点1为根，我们需要保存的信息为当前点子树中颜色出现次数，并且在统计答案的时候找到颜色最多的
这里我们可以用一个桶cnt[i]来记录颜色ii出现的次数，然后用mx来记录当前次数最多的颜色，sum记录次数最多的颜色的次数之和
这样当某种颜色出现次数cnt>mx的时候，我们将mx更新，
并且sum=cnt (为什么不是加上答案呢，因为我们最大值已经更新了，所以实际上是sum=0, sum = sum + cnt)
当cnt=mx的时候，mx不必更新，sum+=cnt
当cnt size[son[u]])
   son[u] = x ;
}
}
void upd(int u , int fa , int k) //将信息加入/撤回
{
//k = 1的时候是加上信息，k = -1的时候是撤回信息
// 记录信息
cnt[colour[u]] += k ;
if(k == 1 && cnt[colour[u]] >= mx) {
   if(cnt[colour[u]] > mx) mx = cnt[colour[u]] , sum = 0 ;
   sum += colour[u] ;
 }
for(auto x : v[u])
 if(x != fa && !vis[x]) upd(x , u , k) ;

}
void dsu(int u , int fa , int keep)//u为当前点, fa为父节点, keep为是否保留信息
{
 for(auto x : v[u]) //先搜我们的轻儿子，过程中不保留信息
  if(x != fa && x != son[u]) dsu(x , u , 0) ;
 if(son[u]) dsu(son[u] , u  , 1) , vis[son[u]] = 1 ;
 upd(u , fa , 1) ;
 // 统计答案
 ans[u] = sum ;
 if(son[u]) vis[son[u]] = 0 ;
 if(!keep) upd(u , fa , -1) , mx = 0 , sum = 0; /*  如果信息不保留，那我们就撤回        */
}

void dfs(int u , int f){
deep[u] = deep[f] + 1 ;
fa[u] = f ;
for(auto x : v[u]){
   if(x != f) {
      dfs(x , u) ;
      size[u] += size[x] ;
      if(!son[u] || size[x] > size[son[u]])
       son[u] = x ;
    }
 }
}
void calc(int u , int keep){
num[deep[u]] += keep ;
sum[deep[u]] += keep * a[u] ;
for(auto x : v[u]) {
  if(x == fa[u] || x == nowson) continue ;
  calc(x , keep) ;
}
}
void query(int u , int lca){
int d = k + 2 * deep[lca] - deep[u] ;
if(d > 0){
  ans[lca] += sum[d] ;
  ans[lca] += num[d] * a[u] ;
}
for(auto x : v[u]){
    if(x == fa[u]) continue ;
    query(x , lca) ;
}
}
void dsu(int u , int fa , int keep){
for(auto x : v[u]){
  if(x == fa || x == son[u]) continue ;
  dsu(x , u , 0) ;
}
if(son[u]) dsu(son[u] , u , 1) , nowson = son[u] ;
for(auto x : v[u]){
   if(x == fa || x == nowson)  continue ;
   query(x , u) ;
   calc(x , 1) ;
 }
 num[deep[u]] += 1 ;
 sum[deep[u]] += a[u] ;
 nowson = 0 ;
 if(!keep) calc(u , -1) ;
}

void FWT_or(int *a,int opt)
{
    for(int i=1;i

ll a[N] , d[N] , n , k , f , c[N] ; 
// 插入线性基
void add(ll x) {
  for(int i = 60 ;i >= 0 ;i -- ) 
     if(x & (1ll << i)) {
        if(d[i]) x ^= d[i] ;
        else {
          d[i] = x ;
          return ;
        }
     }
  f = 1 ;
}
int cnt = 0 ;
// 处理一下线性基，使得出现这种情况
// 1xxxxx0xxxx0xx
//       1xxxx0xx
//            1xx
// 然后便于求异或结果第k小，求第k小只需要k转化为二进制，然后当第i位为1时，ans ^= c[i]
void solve() {
  for(int i = 60 ;i >= 0 ;i -- ) 
    for(int j = i - 1; j >= 0 ; j -- ) {
      if(d[i] & (1ll << j)) 
         d[i] ^= d[j] ;
    }
  for(int i = 0 ;i <= 60 ;i ++ ) 
     if(d[i]) c[cnt ++] = d[i] ;

}
ll get(ll mid) {
  if(f) mid -- ;
  if(mid == 0) return 0 ;
  ll ans = 0 ;
  for(int i = 0 ;i < cnt ;i ++ ) 
    if(mid & (1ll << i)) 
       ans ^= c[i] ;
  return ans ; 
}
int work()
{
  scanf("%lld%lld" , &n , &k) ;
  for(int i = 1; i <= n ;i ++ ) {
     ll x ;
     scanf("%lld" , &x) ;
     add(x) ;
  }
  solve() ;
  ll l = 1 , r = (1ll << cnt) - 1 + f , res = 0 ;
  // 求比k大的异或结果个数，二分加第k小
  while(l <= r) {
    ll mid = l + r >> 1 ;
    if(get(mid) > k) r = mid - 1 ;
    else l = mid + 1 , res = mid ;
  }
  cout << (1ll << cnt) - 1 + f - res << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
*/

ll exgcd(ll a , ll b , ll &x , ll &y){
  if(b == 0){
   	x = 1 , y = 0 ;
   	return a ;
   }
   ll t = exgcd(b , a % b , y , x) ;
   y -= a / b * x ;
   return t ;
}
ll inv(ll a , ll b){
  ll x , y ;
  ll t = exgcd(a , b , x , y) ;
  while(x < 0) x += b ;
  return x ;
}
ll x[N] , m[N] ;
inline ll CRT(){
for(int i = 1; i <= 4 ;i ++ ) m[i] = prime[i] ;
ll M = 1, ans = 0;
for (int i = 1 ; i <= 4; i++)
  M *= m[i];
for (int i = 1; i <= 4; i++)
  ans = (ans + x[i] * (M / m[i]) % M * inv(M / m[i], m[i]) % M) % M;
return ans ;
}

#include
#include
#include
#define IL inline
#define RG register
using namespace std;
typedef long long LL;
const int N=5000005;
const int M=7;
const int PM=2*3*5*7*11*13*17;
int p[N],pi[N];
int phi[PM+1][M+1],sz[M+1];
LL n;
bool f[N];
IL void getprime(){
  for(RG int i=2;ic) continue;
      LL lim=MeiLeh(sqrt2(w));
      for(int j=i;j<=lim;j++)
          sum-=MeiLeh(w/p[j])-(j-1);
  }
  return sum;
}

#define me(x,y) memset(x,y,sizeof x)
#define MIN(x,y) x < y ? x : y
#define MAX(x,y) x > y ? x : y
typedef long long ll;
const int maxn = 1e5+10;
const double INF = 0x3f3f3f3f;
const int MOD = 1e6;
const double eps = 1e-06;
ll Quick_Multiply(ll a,ll b,ll p){  // a*b%p
  ll ans = 0;
  a %= p;
  b %= p;
  if(b < 0) a = -a,b = -b;
  while(b){
      if(b&1) ans = (ans+a)%p;
      b >>= 1;
      a = (a+a)%p;
  }
  ans = (ans+p)%p;
  return ans;
}
ll Quick_Pow(ll a,ll b,ll p){   //a^b%p
  ll ans = 1;
  while(b){
      if(b&1) ans = Quick_Multiply(ans,a,p)%p;
      b >>= 1;
      a = Quick_Multiply(a,a,p)%p;
  }
  return ans;
}
bool Miller_Rabin(ll n){    //Miller_Rabin
  ll i,j,a,x,y,t,u,s = 10;
  if(n == 2 || n == 3) return true;
  if(n < 2 || !(n&1)) return false;
  for(t = 0,u = n-1;!(u&1); t++,u>>=1);   //n-1 = u*2^t
  for(i = 0; i < s; i++){
      a = rand()%(n-1)-1;
      x = Quick_Pow(a,u,n);   //a^u
      for(j = 0; j < t; j++){
          y = Quick_Multiply(x,x,n);  //x^2
          if(y == 1 && x != 1 && x != n-1) return false;  //???????
          x = y;
      }
      if(x != 1) return false;    //????С????
  }
  return true;
}

ll factor[maxn];
int tot;
ll muti_mod(ll a,ll b,ll c){    //????(a*b) mod c,a,b,c<2^63
  a%=c , b%=c;
  ll ret=0;
  while (b){
      if (b&1){
          ret+=a;
          if (ret>=c) ret-=c;
      }
      a<<=1;
      if (a>=c) a-=c;
      b>>=1;
  }
  return ret;
}
ll pow_mod(ll x,ll n,ll mod){  //????x^n mod c ,??????
  if (n==1) return x%mod;
  int bit[64],k=0;
  while (n){
      bit[k++]=n&1;
      n>>=1;
  }
  ll ret=1;
  for (k=k-1;k>=0;k--){
      ret=muti_mod(ret,ret,mod);
      if (bit[k]==1) ret=muti_mod(ret,x,mod);
  }
  return ret;
}
bool check(ll a,ll n,ll x,ll t){   //??a?????n-1=x*2^t??????n????????
  ll ret=pow_mod(a,x,n),last=ret;
  for (int i=1;i<=t;i++){
      ret=muti_mod(ret,ret,n);
      if (ret==1 && last!=1 && last!=n-1) return 1;
      last=ret;
  }
  if (ret!=1) return 1;
  return 0;
}
bool Miller_Rabin(ll n){
  ll x=n-1,t=0;
  while ((x&1)==0) x>>=1,t++;
  bool flag=1;
  if (t>=1 && (x&1)==1){
      for (int k=0;k=n) p=Pollard_rho(p,rand() % (n-1) +1);
  findfac(p);
  findfac(n/p);
}
int idx = 0 ;
struct node
{
  ll val , num ;
  node() {}
  node(ll val , ll num) : val(val) , num(num) {} 
  bool operator<(const node &a) const 
  {
  	val < a.val ;
  }
}fac[maxn];
void solve(ll n)
{
  if (!Miller_Rabin(n)) printf("Prime\n");
  else{
          tot = 0;
          findfac(n);
          sort(factor , factor + tot) ;
          idx = 0 ;
          for(int i = 0 ; i < tot ;i ++)
           {
           	if(factor[i] != fac[idx].val) 
           	 fac[++ idx] = {factor[i] , 1};
           	else 
           	 fac[idx].num ++ ;
  		 }
      }
}
int main(){
  srand(time(NULL));
  int t;
  scanf("%d",&t);
  while (t--){
      ll n;
      scanf("%I64d",&n);
  	solve(n) ;
      for(int i = 1; i <= idx ;i ++)
       cout << fac[i].val << " " << fac[i].num << endl ;
  }
}

ll k;
ll check(ll v, ll n, ll ndr, ll nv) {
  return v >= ndr ? (n / v - 1) : (nv - v);
}
// ll S[10000000];
// ll V[10000000];
ll primenum(ll n) // O(n^(3/4))
{
ll r = (ll)sqrt(n);
ll ndr = n / r;
assert(r*r <= n && (r+1)*(r+1) > n);
ll nv = r + ndr - 1;
std::vector S(nv+1);
std::vector V(nv+1);
for(ll i=0;i S[nv-p+1]) {
    ll sp = S[nv-p+1]; // sum of primes smaller than p
    ll p2 = p*p;
    for(ll i=0;i= p2) {
        S[i] -= 1LL  * (S[check(V[i] / p, n, ndr, nv)] - sp);// //求素数个数
      }
      else break;
    }
  }
}
return S[0];
}
ll primesum(ll n) // O(n^(3/4)){
ll r = (ll)sqrt(n);
ll ndr = n / r;
assert(r*r <= n && (r+1)*(r+1) > n);
ll nv = r + ndr - 1;
std::vector S(nv+1);
std::vector V(nv+1);
for(ll i=0;i S[nv-p+1]) {
    ll sp = S[nv-p+1]; // sum of primes smaller than p
    ll p2 = p*p;
    for(ll i=0;i= p2) 
        S[i] -= p* (S[check(V[i] / p, n, ndr, nv)] - sp); //求素数和
      else break;
  }
}
return S[0];
}

void solve(){
for (int i=1;i<=n;i++) a[i][0]=r[i];
   for (int l=1;(1<

const int mod=998244353;
template
inline int pow(int x,T y)
{
  rg int res=1;x%=mod;
  for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)res*x%mod;
  return res;
}
inline int Quadratic_residue(const int a)
{
  if(a==0)return 0;
  int b=(rand()<<14^rand())%mod;
  while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;
  int s=mod-1,t=0,x,inv=pow(a,mod-2),f=1;
  while(!(s&1))s>>=1,t++,f<<=1;
  t--,x=pow(a,(s+1)>>1),f>>=1;
  while(t)
  {
  	f>>=1;
  	if(pow((int)((ll)inv*x%mod*x%mod),f)!=1)x=(ll)x*pow(b,s)%mod;
  	t--,s<<=1;
  }
  return min(x,mod-x);
}

vector add(vector A,vector B){
  vector C;
  int t=0;
  for(int i=0;i muti(vector A,int b){
  vector C;
  int t=0;
  for(int i=0;i A,vector B){
  if(A.size()!=B.size())  return A.size()>B.size();
  for(int i=A.size();i>=0;i--)
      if(A[i]!=B[i])
          return A[i]>B[i];
  return true;
}
vector div(vector A, int b, int &r){
  vector C;
  r = 0;
  for (int i = A.size() - 1; i >= 0; i -- ) {
      r = r * 10 + A[i];
      C.push_back(r / b);
      r %= b;
  }
  reverse(C.begin(), C.end());
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}
vector sub(vector A,vector B){
  vector C;
  int t=0;
  for(int i=0;i1&&C.back()==0) C.pop_back();
  return C;
}
void print(vector a){
for(int i = a.size() - 1; i >= 0 ;i --) cout << a[i]  ;
puts("") ;
return ;
}

void get_prime(int n){
  for(int i = 2;i <= n;i ++) {
       if(!st[i]) prime[tot ++] = i ;
       for(int j = 0; j < tot && i * prime[j] <= n ;j ++){
            st[i * prime[j]] = true ;
            if(i % prime[j] == 0) break ;
        }
   }
   return ;
}
int get(int a , int p){
  int sum = 0 ;
  while(a){
       sum += a / p ;
       a /= p ;
  }
  return sum ;
}
vector muti(vector a , int b){
  int t = 0 ;
  vector res ;
  for(int i = 0;i < a.size() ;i ++){
      t += a[i] * b ;
      res.push_back(t % 10) ;
      t /= 10 ;
  }
  while(t){
      res.push_back(t % 10) ;
      t /= 10 ;
  }
  return res ;
}
int main(){
  int a , b ;
  cin >> a >>  b ;
  get_prime(a);
  for(int i = 0; i < tot ;i ++){
       int p = prime[i] ;
       sum[i] = get(a,p) - get(b,p) - get(a-b , p);
   }
   vector res; 
   res.push_back(1);
   for(int i = 0;i < tot ; i ++)
    for(int j = 0; j < sum[i] ;j ++)
     res = muti(res, prime[i]);
   for(int i = res.size() - 1;i >= 0;i --)
    cout << res[i]  ;
   cout << endl ;
  return 0;
}

#define D double
D a[maxn][maxn];
int n;
int main(){
  scanf("%d",&n);
  for(re int i=1;i<=n;++i){
  	for(re int j=1;j<=n+1;++j){
  		scanf("%lf",&a[i][j]);
  	}
  }
  for(re int i=1;i<=n;++i)//枚举列（项）{
  	re int max=i;
  	for(re int j=i+1;j<=n;++j)//选出该列最大系数
  		if(fabs(a[j][i])>fabs(a[max][i]))
          //fabs是取浮点数的绝对值的函数
  			max=j;
  	for(re int j=1;j<=n+1;++j)//交换
  		swap(a[i][j],a[max][j]);
  	if(!a[i][i])//最大值等于0则说明该列都为0，肯定无解{
  		puts("No Solution");
  		return 0;
  	}
  	for(re int j=1;j<=n;++j)//每一项都减去一个数（就是小学加减消元）{
  		if(j!=i){
  			re D temp=a[j][i]/a[i][i];
  			for(re int k=i+1;k<=n+1;++k){
  				a[j][k]-=a[i][k]*temp;
                  //a[j][k]-=a[j][i]*a[i][k]/a[i][i];
  			}
  		}
  	}
  }
  //上述操作结束后，矩阵会变成这样
  /*
  k1*a=e1
  k2*b=e2
  k3*c=e3
  k4*d=e4
  */
  //所以输出的结果要记得除以该项系数，消去常数
  for(re int i=1;i<=n;++i)
  {
  	printf("%.2lf\n",a[i][n+1]/a[i][i]);
  }
  return 0;
}

#include 
using namespace std ;
//返回数组a中当下顺序的康拖映射
typedef unsigned long long ll ;
ll b[30] ;
//对前 10 个自然数(0 ~ 9)的阶乘存入表
//以免去对其额外的计算
ll fact[22] ;
/**
* @brief 康拓展开
*
* @param[in] permutation 输入的一个全排列
* @param[out] num 输入的康拓映射，即是第几个全排列
*/
ll contor(vector permutation) {
  ll num = 0;
  ll len = permutation.size();
  for (ll i = 0; i < len; ++i) {
      ll cnt = 0; // 在 i 之后，比 i 还小的有几个
      for (ll j = i + 1; j < len; ++j)
          if (permutation[i] > permutation[j]) ++cnt;
      num += cnt * fact[len - i - 1];
  }
  return num + 1;
}
//对前 10 个自然数(0 ~ 9)的阶乘存入表
//以免去对其额外的计算
/**
* @brief 逆康拓展开
*
* @param[in] bits 给定全排列的使用数字个数
* @param[in] num 给定全排列的次位
* @param[out] permutation 输出对应的全排列
*/
vector revContor(ll bits, ll num) {
  num = num - 1; //有 num - 1 个排列比目标序列要小
  vector vis(bits + 1, false);
  vector permutation(bits, -1);

  ll n, residue = num;
  for (ll i = 0; i < bits; ++i) {
      n = residue / (fact[bits - i - 1]);
      residue = residue % (fact[bits - i - 1]);

      for (ll j = 1; j <= bits; ++j) {
          if (!vis[j] && !(n--)) {
              vis[j] = true;
              permutation[i] = j;
              break;
          }
      }
  }
  return permutation;
}
int main()
{
int n , m ;
cin >> n >> m ;
fact[0] = 1;
for(ll i = 1; i <= n ;i ++)
 fact[i] = fact[i - 1] * i ;
for(int i = 1; i <= m ;i ++)
 {
   char s[2] ;
   cin >> s ;
   if(s[0] == 'P') // 求第x大的字典序
    {
      ll x ;cin >> x ;
      vector t = revContor(n , x) ;
      for(auto xx : t)
       cout << xx << " " ;
      puts("") ;
    }
    else      // 求字典序第几大
     {
       vector b ;
       for(ll i = 1 , x ; i <= n ;i ++) cin >> x , b.push_back(x) ;
       cout << contor(b) << endl ;
     }
 }
return 0 ;
}

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

ll exgcd(ll a,ll b,ll &x,ll &y){
  if(b==0){
  	x=1;
  	y=0;
  	return a;
  }
  ll q=exgcd(b,a%b,x,y);
  ll t=x;
  x=y;
  y=t-a/b*y;
  return q;
}
ll gcd(ll a , ll b)
{
return b == 0 ? a : gcd(b , a % b) ;
}
ll tx , ty , tz ;
// 求正整数
void get(ll a , ll b , ll d)
{
  ll x , y ;
  int md=exgcd(a,b,x,y);
  a/=md,b/=md,d/=md;
  int x1=x*d;
x1=(x1%b+b)%b;
ll y1=(d-a*x1)/b;
y1=abs(y1);
ll y2=y*d;
y2=(y2%a+a)%a;
int x2=(d-b*y2)/a;
x2=abs(x2);
if(x1+y1

for(int i = 1; i <= m ;i ++ ) {
int a , b , c , d , e , f ;
// a <= x <= d , b <= y <= e , c <= z <= f
cin >> a >> b >> c >> d >> e >> f ;
sum[a][b][c] ++ ;
sum[a][e + 1][c] -- ;
sum[d + 1][b][c] -- ;
sum[a][b][f + 1] -- ;
sum[d + 1][b][f + 1] ++ ;
sum[a][e + 1][f + 1] ++ ;
sum[d + 1][e + 1][c] ++ ;
sum[d + 1][e + 1][f + 1] -- ;
}
for(int i = 1; i <= n ;i ++ ) {
for(int j = 1; j <= n ;j ++ ) {
  for(int k = 1; k <= n ;k ++ ) {
    sum[i][j][k] += sum[i - 1][j][k] + sum[i][j - 1][k] + sum[i][j][k - 1] + sum[i - 1][j - 1][k - 1] - sum[i - 1][j - 1][k] - sum[i - 1][j][k - 1] - sum[i][j - 1][k - 1] ;
  }
}
}

struct Point{
	double x,y,t,d;
	Point(double _x=0,double _y=0,double _t=0,double _d=0){
		x=_x;y=_y;t=_t;d=_d;
	}
};
Point operator + (const Point &a,const Point &b){
  return Point(a.x+b.x,a.y+b.y);
}
Point operator - (const Point &a,const Point &b){
  return Point(a.x-b.x,a.y-b.y);
}
double operator ^ (Point a,Point b){
  return a.x*b.y-a.y*b.x;
}
double Dis(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double RotateCalipers(Point *ch,int n){//传入点集和集合元素个数 
	double ans=- INF;int q=1;
	ch[n]=ch[0];
	for(int i=0;i

const int maxh=62;
#define rint register int
int cmp(double x){
   if(fabs(x)0) return 1;
   return -1;
}
double sqr(double x){
   return x*x;
}
struct point {
   double x,y;
   point(){}
   point(double a,double b):x(a),y(b){}
   void input(){
       cin>>x>>y;
   }
   friend point operator -(const point &a,const point &b){
       return point (a.x-b.x,a.y-b.y);
   }
   friend point operator *(const point &a,const double &b){
       return point (a.x*b,a.y*b);
   }
   friend point operator *(const double &b,const point &a){
       return point (a.x*b,a.y*b);
   }
   friend point operator /(const point &a,const double &b){
       return point (a.x/b,a.y/b);
   }
};
double cross(const point &a,const point &b){
   return a.x*b.y-a.y*b.x;
}
struct line {
   point a,b;
   line(){}
   line(point x,point y):a(x),b(y){}
   void input(){
       a.input();
       b.input();
   }
}a[N];
bool parallel(line a,line b){
   return !cmp(cross(a.a-a.b,b.a-b.b));
}
bool line_make_point(line a,line b,point &res){
   if(parallel(a,b)) return false;
   double s1=cross(a.a-b.a,b.b-b.a);
   double s2=cross(a.b-b.a,b.b-b.a);
   res=(s1*a.b-s2*a.a)/(s1-s2);
   return true;
}
double res=0;
int main() {
   cin>>n;
   for(int i=1;i<=n;i++){
       a[i].input();
   }
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           for(int k=1;k<=n;k++){
               point x,y,z;
               if(!line_make_point(a[i],a[j],x)) continue;
               if(!line_make_point(a[i],a[k],y)) continue;
               if(!line_make_point(a[j],a[k],z)) continue;
               double b,c,d;
               b=sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));
               c=sqrt(sqr(x.x-z.x)+sqr(x.y-z.y));
               d=sqrt(sqr(y.x-z.x)+sqr(y.y-z.y));
               double p=(b+c+d);
               res=max(res,p/*sqrt(p*(p-b)*(p-c)*(p-d))*/);
           }
   if(abs(res)

struct node
{
 int x , y , r ;
}p[6] , z[6];
int check1(node a){
 if(a.x > z[0].x && a.x < z[1].x && a.y > z[0].y && a.y < z[3].y) return 1 ;
 for(int i = 0 ;i < 4 ;i ++){
    if(z[i].x == z[i + 1].x)
       if(a.x == z[i].x && a.y >= min(z[i].y , z[i + 1].y) && a.y <= max(z[i].y , z[i + 1].y)) return 2 ;
    if(z[i].y == z[i + 1].y)
       if(a.y == z[i].y && a.x >= min(z[i].x , z[i + 1].x) && a.x <= max(z[i].x , z[i + 1].x)) return 2 ;
  }
 return 0 ;
}
int check2(node a){
 int t = (p[0].x - a.x) * (p[0].x - a.x) + (p[0].y - a.y) * (p[0].y - a.y) ;
 if(t == p[0].r * p[0].r) return 2 ;
 if(t < p[0].r * p[0].r) return 1 ;
 return 0 ;
}
bool have(){
 for(int i = 0 ;i <= 4 ;i ++)
  if(check1(p[i]) == 1)  return 1 ;
 for(int i = 0 ;i < 4;i ++)
  if(check2(z[i]) == 1)  return 1 ;
 return 0 ;
}
bool touch(){
 for(int i = 0 ;i <= 4 ;i ++)
  if(check1(p[i]) == 2) return 1 ;
 for(int i = 0 ;i < 4 ;i ++)
  if(check2(z[i]) == 2) return 1 ;
 return 0 ;
}
int main(){
 int r ;
 cin >> p[0].x >> p[0].y >> p[0].r ;
 p[1].x = p[0].x + p[0].r , p[1].y = p[0].y ;
 p[2].x = p[0].x , p[2].y = p[0].y + p[0].r ;
 p[3].x = p[0].x - p[0].r , p[3].y = p[0].y ;
 p[4].x = p[0].x , p[4].y = p[0].y - p[0].r ;
 cin >> z[0].x >> z[0].y >> r;
 z[1].x = z[0].x + r , z[1].y = z[0].y ;
 z[2].x = z[0].x + r , z[2].y = z[0].y + r ;
 z[3].x = z[0].x , z[3].y = z[0].y + r ;
 z[4] = z[0] ;
 if(have()) puts("2") ;
 else if(touch()) puts("1") ;
 else puts("0") ;
 return 0 ;
}

struct Point{    double x, y;
   Point() {}
   Point(double xx, double yy)
   {
       x = xx;
       y = yy;
   }
   Point operator-(Point s) { return Point(x - s.x, y - s.y); }
   Point operator+(Point s) { return Point(x + s.x, y + s.y); }
   double operator*(Point s) { return x * s.x + y * s.y; }
   double operator^(Point s) { return x * s.y - y * s.x; }
} p[M];
double max(double a, double b) { return a > b ? a : b; }
double min(double a, double b) { return a < b ? a : b; }
double len(Point a) { return sqrt(a * a); }  // 向量 a 的长度
double dis(Point a, Point b) { return len(b - a); } // a 与 b 之间的距离
double cross(Point a, Point b, Point c)             // (a , b) ^ (a , c){
   return (b - a) ^ (c - a);
}
double dot(Point a, Point b, Point c) // (a , b) * (a , c)
{
   return (b - a) * (c - a);
}
int judge(Point a, Point b, Point c) // 判断 点c 是否在 线段 ab 上
{
   if (c.x >= min(a.x, b.x) && c.x <= max(a.x, b.x) && c.y >= min(a.y, b.y) && c.y <= max(a.y, b.y))
       return 1;
   return 0;
}
double area(Point b, Point c, double r) // 圆心 a ， 半径 r ， 与三角形 a , b , c 相交的面积
{
   Point a(0.0, 0.0);
   if (dis(b, c) < eps)
       return 0.0;
   double h = fabs(cross(a, b, c)) / dis(b, c);
   if (dis(a, b) > r - eps && dis(a, c) > r - eps){
       double angle = acos(dot(a, b, c) / dis(a, b) / dis(a, c));
       if (h > r - eps)
           return 0.5 * r * r * angle;
       else if (dot(b, a, c) > 0 && dot(c, a, b) > 0){
           double angle1 = 2 * acos(h / r);
           return 0.5 * r * r * fabs(angle - angle1) + 0.5 * r * r * sin(angle1);
       }
       else return 0.5 * r * r * angle;
   }
   else if (dis(a, b) < r + eps && dis(a, c) < r + eps) return 0.5 * fabs(cross(a, b, c));
   else{
       if (dis(a, b) > dis(a, c))swap(b, c);
       if (fabs(dis(a, b)) < eps) return 0.0;
       if (dot(b, a, c) < eps) {
           double angle1 = acos(h / dis(a, b));
           double angle2 = acos(h / r) - angle1;
           double angle3 = acos(h / dis(a, c)) - acos(h / r);
           return 0.5 * dis(a, b) * r * sin(angle2) + 0.5 * r * r * angle3;
       }
       else{
           double angle1 = acos(h / dis(a, b));
           double angle2 = acos(h / r);
           double angle3 = acos(h / dis(a, c)) - angle2;
           return 0.5 * r * dis(a, b) * sin(angle1 + angle2) + 0.5 * r * r * angle3;
       }
   }
}
int main(){
   int n = 4;
   double rx, ry, R;
   scanf("%lf%lf%lf", &rx, &ry, &R);
   scanf("%lf%lf%lf%lf", &p[1].x, &p[1].y, &p[3].x, &p[3].y);
   p[2].x = p[1].x;
   p[2].y = p[3].y;
   p[4].x = p[3].x;
   p[4].y = p[1].y;
   p[5] = p[1];
   Point O(rx, ry);
   for (int i = 1; i <= n + 1; i++)
       p[i] = p[i] - O;
   O = Point(0, 0);
   double sum = 0;
   for (int i = 1; i <= n; i++){
       int j = i + 1;
       double s = area(p[i], p[j], R);
       if (cross(O, p[i], p[j]) > 0) sum += s;
       else sum -= s;
   }
   printf("%.4lf\n", fabs(sum));
}

double direction( node p1,node p2,node p ){
   return ( p1.x -p.x )*( p2.y-p.y) -  ( p2.x -p.x )*( p1.y-p.y)   ;
}
int on_segment( node p1,node p2 ,node p ){
   double max=p1.x > p2.x ? p1.x : p2.x ;
   double min =p1.x < p2.x ? p1.x : p2.x ;
double max1=p1.y > p2.y ? p1.y : p2.y ;
   double min1=p1.y < p2.y ? p1.y : p2.y ;
   if( p.x >=min && p.x <=max &&
 p.y >=min1 && p.y <=max1 )
       return 1;
   else
       return 0;
}
bool check1(node p1 , node p2 , node q){
 if( !on_segment( p1,p2,q ) ) return 0 ;
 if( direction( q,p1,p2 )==0 )return 1 ;
 else return 0 ;
}
bool check(int x ,int y){
 for(int i = 1; i <= n ;i ++)
  if(x != i && y != i && check1(a[x] , a[y] , a[i])) return 0 ;
 for(int i = 1; i <= n ;i ++)
    if(check1(a[x] , a[y] , b[i]))
     return 0 ;
 return 1 ;
}

// 直线相交求交点 ， 凸包算法， 求点是否在多边形范围内
struct point {
   double x,y;
   point(){}
   point(double a,double b):x(a),y(b){}
   void input(){
       cin>>x>>y;
   }
   friend point operator -(const point &a,const point &b){
       return point (a.x-b.x,a.y-b.y);
   }
   friend point operator *(const point &a,const double &b){
       return point (a.x*b,a.y*b);
   }
   friend point operator *(const double &b,const point &a){
       return point (a.x*b,a.y*b);
   }
   friend point operator /(const point &a,const double &b){
       return point (a.x/b,a.y/b);
   }
}p[N] , s[N] ;
struct line {
   point a,b;
   line(){}
   line(point x,point y):a(x),b(y){}
   void input(){
       a.input();
       b.input();
   }
}a[N];
int cmp(double x){
   if(fabs(x)0) return 1;
   return -1;
}
double sqr(double x){
   return x*x;
}
double cross(const point &a,const point &b){
   return a.x*b.y-a.y*b.x;
}
bool parallel(line a,line b){
   return !cmp(cross(a.a-a.b,b.a-b.b));
}
bool line_make_point(line a,line b,point &res){
   if(parallel(a,b)) return false;
   double s1=cross(a.a-b.a,b.b-b.a);
   double s2=cross(a.b-b.a,b.b-b.a);
   res=(s1*a.b-s2*a.a)/(s1-s2);
   return true;
}
double dis(point a,point b)
{
   point c=a-b;
   return sqrt(c.x*c.x+c.y*c.y);
}
double cross(point &a,point &b)//叉乘{
   return a.x*b.y-a.y*b.x;
}
bool cmp(point a,point b)//极角排序{
   double x=cross(a-p[1],b-p[1]);//以p[1]为积点

   if(x>0) return 1;//让a处于b的顺时针
   if(x==0&&dis(a,p[1])0) f++;
   }
   //if(cross(s[1]-s[n],a-s[n])>0) f++;
   if(f==n) return 1;
   return 0;
}
// 先按照x ， 然后y
bool cmp2(point a,point b){
   if (a.x!=b.x)
       return a.x1&&mulx(s[m-2],s[m-1],p[i])<=0) m--;
     s[m++]=p[i];
 }
 int kk=m;
 for(int i=n-2;i>=0;i--){
     while(m>kk&&mulx(s[m-2],s[m-1],p[i])<=0) m--;
     s[m++]=p[i];
 }
 if(n>1)
     m--;
}

/*
题意：一个长度为n的数组，求任意[ L,R ]区间和为S的总数。
题解：01背包
dp[N]代表前i个数中和为N的数量
每次dp[0]+=1，我们01背包板子循环到第i个物品求的是前i个物品和为N的数量，并没有
[2,i]、[3，i]、[4，i]、…、[i，i]这些情况，少了i-1种情况答案肯定不对，所以我们只需要把dp[0]赋值为 1 + （i-1） 原始就为1，再加上少的i-1中情况。
*/
ll a[maxn],dp[maxn];
int main(){
  ll n,k;
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>a[i];
  ll ans=0;
  for(int i=1;i<=n;i++){
  	dp[0]+=1;//[2,i]、[3，i]、[4，i]、...、[i，i]
  	for(int j=k;j>=a[i];j--)
  		dp[j]=(dp[j]+dp[j-a[i]])%mod;
  	ans=(ans+dp[k])%mod;//前i个数的和为K的数量
  }
  cout<

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector VI;
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll n;
namespace linear_seq {
  const int N=10010;
  ll res[N],base[N],_c[N],_md[N];
  vector Md;
  void mul(ll *a,ll *b,int k) {
      rep(i,0,k+k) _c[i]=0;
      rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
      for (int i=k+k-1;i>=k;i--) if (_c[i])
          rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
      rep(i,0,k) a[i]=_c[i];
  }
  int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
      ll ans=0,pnt=0;
      int k=SZ(a);
      assert(SZ(a)==SZ(b));
      rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
      Md.clear();
      rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
      rep(i,0,k) res[i]=base[i]=0;
      res[0]=1;
      while ((1ll<=0;p--) {
          mul(res,res,k);
          if ((n>>p)&1) {
              for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
              rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
          }
      }
      rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
      if (ans<0) ans+=mod;
      return ans;
  }
  VI BM(VI s) {
      VI C(1,1),B(1,1);
      int L=0,m=1,b=1;
      rep(n,0,SZ(s)) {
          ll d=0;
          rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
          if (d==0) ++m;
          else if (2*L<=n) {
              VI T=C;
              ll c=mod-d*powmod(b,mod-2)%mod;
              while (SZ(C)v;
  v.push_back(3);
  v.push_back(9);
  v.push_back(20);
  v.push_back(46);
  v.push_back(106);
  v.push_back(244);
  v.push_back(560);
  v.push_back(1286);
  v.push_back(2956);
  v.push_back(6794);
  int nCase;
  scanf("%d", &nCase);
  while(nCase--){
      scanf("%lld", &n);
      printf("%lld\n",1LL * linear_seq::gao(v,n-1) % mod);
  }
}

ll len[N] , ans[N] , fw[N] , w[N] ;
int l1[N] , l2[N] , fa[N]  , e[N] , ne[N] , idx , h[N] ;
void add(int a, int b , int c){
  e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx ++ ;
}
void init(){
  memset(len , 0 , sizeof len) ;
  memset(l1 , 0 , sizeof l1) ;
  memset(l2 , 0 , sizeof l2) ;
  memset(ans , 0 , sizeof ans) ;
  memset(fa , 0 , sizeof fa) ;
  memset(fw , 0 , sizeof fa) ;
  memset(h , -1 , sizeof h) ;
  idx = 0 ;
}
void dfs1(int u){
  for(int i = h[u] ; ~i ; i = ne[i]){
     int v = e[i] ;
     dfs1(v) ;
     if(len[v] + w[i] > len[l1[u]] + fw[l1[u]]) l2[u] = l1[u] , l1[u] = v , len[u] = len[v] + w[i] ;
     else if(len[v] + w[i] > len[l2[u]] + fw[l2[u]]) l2[u] = v ;
   }
}
void dfs2(int u , ll fal = 0){
  ans[u] = max(len[u] , fal) ;
  for(int i = h[u] ; ~i ; i = ne[i]){
     int v = e[i] ;
     if(v == l1[u]) dfs2(v , max(fal + w[i] , len[l2[u]] + fw[l2[u]] + w[i])) ;
     else dfs2(v , max(fal + w[i] , len[l1[u]] + fw[l1[u]] + w[i])) ;
   }
}
int work()
{
  int n ;
  cin >> n ;
  init() ;
  for(int i = 2 , x ; i <= n ;i ++)
      fa[i] = read() , fw[i] = read() , add(fa[i] , i , fw[i]) ;
  dfs1(1) , dfs2(1) ;
  for(int i = 1; i <= n ;i ++)  cout << ans[i] << endl ;
  return 0 ;
}

int h[N] , rh[N] , e[N] , ne[N] , w[N] , idx;
void add(int *h , int a , int b , int c){
   e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx ++ ;
}
int S , T , K ;
int dis[N] , f[N] , n , m , st[N] ;
void dij(){
   priority_queue , greater > q ;
   memset(dis , 0x3f , sizeof dis) ;
   dis[T] = 0 ;
   memset(st , 0 , sizeof st) ;
   q.push({0 , T}) ;
   while(q.size()){
        auto t = q.top() ; q.pop() ;
        int u = t.second ;
        if(st[u]) continue ;
        st[u] = 1 ;
        for(int i = rh[u] ; ~i ; i = ne[i]){
             int v = e[i] ;
             if(dis[v] > dis[u] + w[i])
              dis[v] = dis[u] + w[i] , q.push({dis[v] , v}) ;
         }
    }
    memcpy(f , dis , sizeof f) ;
    return ;
}
int a_star(){
   priority_queue , greater > q ;
   q.push({f[S] , {0 , S}}) ;
   memset(st , 0 , sizeof st) ;
   while(q.size()){
        auto t = q.top() ; q.pop() ;
        int u = t.second.second , distance = t.second.first ;
       
        if(st[u] >= K) continue ;
        st[u] ++ ;
        if(u == T && st[u] == K) return distance ;
        for(int i = h[u] ; ~i ; i = ne[i]){
             int v = e[i] ;
             if(st[v] < K)
              q.push({distance + w[i] + f[v] , {distance + w[i] , v}}) ;
         }
    }
    return -1 ;
}
int main(){
 n = in() , m = in() ;
 memset(h , -1 , sizeof h ) , memset(rh , -1 , sizeof rh) ;
 for(int i = 1 , a , b , c ; i <= m ;i ++)
      a = in() , b = in() , c = in() 
     , add(h , a , b , c) , add(h , b , a , c) 
     , add(rh , b , a , c) , add(rh , a , b , c) ;
 S = 0 , T = n - 1 , K = 2 ;
 if(S == T) K ++ ;
 dij() ;
 memset(st , 0 , sizeof st) ;
 int t = a_star() ;
 cout << t << endl ;
 return 0 ;
}
/*
*/