• 个人简介

    $${\Huge \mathrm{TYOI}+=\sum_{i=2022}^{+\infty}\mathrm{me}_{i}} $$

    希望大家一直记得我。
    “希望大家永远忘了我。”

    我该在哪里停留？我问我自己。

    生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

    你不可能一直走上坡路到达最高的山峰

    洛谷账号

    图论编辑器

    计算器套件 - GeoGebra

    好用的插件

    Oier

    CP Editor

    新时代神题

    CTF-OK100.PNG

    新时代神贴

    Person-of-the-time.png

    学术
    常用积分公式表 $$\int k dx=kx+C \\ \int x^{\mu} dx=\frac{x^{\mu+1}}{\mu+1}+C\space (\mu\ne -1) \\ \int \frac{1}{x} dx=\ln |x|+C $$
    Tarjan求scc 
    void tarjan(int u)
{
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u,in_stk[u]=true;
	for (int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if (in_stk[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	
	if (dfn[u]==low[u])
	{
		scc_cnt++;
		int v;
		do
		{
			v=stk[top--];
			in_stk[v]=false;
		} while (v!=u);
	}
}
    Tarjan求缩点 
    void tarjan(int u)
{
	dfn[u]=low[u]=++timestamp;
	int flag=0;
	for (int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if (low[v]>=dfn[u]) 
			{
				flag++;
				if (u!=root || flag>1) 
				{
					cut[u]=true;
				}
			}
		}
		else
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
}
    Tarjan求桥 
    void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++timestamp;
	for (int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i];
		if (!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if (dfn[u]<low[v])
			{
				bridge[i]=bridge[i^1]=true;
			}
		}
		else if (v!=fa) low[u]=min(low[u],dfn[v]);
	}
}
    中缀表达式处理 
    #include <iostream>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <stack> //用栈存表达式树
#include <unordered_map> //运算符优先级，用哈希表

using namespace std;

const int N=100010;

string s;
stack<int> num; //存数字的
stack<char> op; //存运算符的

unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}};

void calc()
{
    int b=num.top();
    num.pop();
    int a=num.top();
    num.pop();
    
    char c=op.top();
    op.pop();
    
    int res;
    if (c=='+') res=a+b;
    if (c=='-') res=a-b;
    if (c=='*') res=a*b;
    if (c=='/') res=a/b;
    if (c=='^') res=pow(a,b);
    
    num.push(res);
}

int main()
{
    cin >> s;
    for (int i=0;i<s.length();i++)
    {
        char c=s[i];
        if (isdigit(c))
        {
            int n=0,j=i;
            while (isdigit(s[j]) && j<s.length()) 
            {
                n=n*10+s[j]-'0';
                j++;
            }
            num.push(n);
            i=j-1;
        }
        else if (c=='(') op.push(c);
        else if (c==')')
        {
            while (op.size() && op.top()!='(')
            {
                calc();
            }
            op.pop();
        }
        else
        {
             while (op.size() && pr[op.top()]>=pr[c]) 
             {
                 calc();
             }
             op.push(c);
        }
    }
    
    while (op.size()) calc();
    
    cout << num.top() << endl;

    return 0;
}
    对拍合集

    testlib_for_lemons.h

    Selfeval

    @echo off
maker.exe
mine.exe
std.exe
fc mine.out std.out
if %ERRORLEVEL% NEQ 0 (
    pause
)
%0
    树链剖分 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=100010,M=2*N;
typedef long long ll; 
int n;
int w[N];
int h[N],e[M],ne[M],idx;
int dfn[N],timestamp;
int nw[N];
int depth[N],sz[N],fa[N],son[N],top[N];
struct node
{
    int l,r;
    ll sum,add;
} tr[N*4];

void add(int u,int v)
{
    e[idx]=v;
    ne[idx]=h[u],h[u]=idx++;
}

void dfs1(int u,int fat,int dep)
{
    fa[u]=fat,depth[u]=dep,sz[u]=1;
    for (int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if (v==fat) continue;
        dfs1(v,u,dep+1);
        sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
}

void dfs2(int u,int t)
{
    dfn[u]=++timestamp;
    nw[dfn[u]]=w[u];
    top[u]=t;
    if (!son[u]) return;
    dfs2(son[u],t);
    
    for (int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if (v==fa[u]) continue;
        if (v==son[u]) continue;
        dfs2(v,v);
    }
}

void pushup(int u)
{
    tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}

void pushdown(int u)
{
    node &root=tr[u],&left=tr[u*2],&right=tr[u*2+1];
    if (root.add)
    {
        left.sum+=(left.r-left.l+1)*root.add;
        left.add+=root.add;
        
        right.sum+=(right.r-right.l+1)*root.add;
        right.add+=root.add;
        
        root.add=0;
    }
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r;
    tr[u].add=0;
    if (l==r)
    {
        tr[u].sum=nw[l];
        return;
    }
    int mid=l+(r-l)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int d)
{
    if (l<=tr[u].l && tr[u].r<=r) 
    {
        tr[u].sum+=(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+(tr[u].r-tr[u].l)/2;
    if (l<=mid) modify(u*2,l,r,d);
    if (r>mid) modify(u*2+1,l,r,d);
    pushup(u);
}

ll query(int u,int l,int r)
{
    if (l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+(tr[u].r-tr[u].l)/2;
    ll res=0;
    if (l<=mid) res+=query(u*2,l,r);
    if (r>mid) res+=query(u*2+1,l,r);
    return res;
}

void modify_path(int u,int v,int k)
{
    while (top[u]!=top[v])
    {
        if (depth[top[u]]<depth[top[v]]) swap(u,v);
        modify(1,dfn[top[u]],dfn[u],k);
        u=fa[top[u]];
    }
    if (depth[u]<depth[v]) swap(u,v);
    modify(1,dfn[v],dfn[u],k);
}

void modify_tree(int u,int k)
{
    modify(1,dfn[u],dfn[u]+sz[u]-1,k);
}

ll query_path(int u,int v)
{
    ll res=0;
    while (top[u]!=top[v])
    {
        if (depth[top[u]]<depth[top[v]]) swap(u,v);
        res+=query(1,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    if (depth[u]<depth[v]) swap(u,v);
    res+=query(1,dfn[v],dfn[u]);
    return res;
}

ll query_tree(int u)
{
    return query(1,dfn[u],dfn[u]+sz[u]-1);
}

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> w[i];
    memset(h,-1,sizeof(h));
    for (int i=1;i<=n-1;i++)
    {
        int u,v;
        cin >> u >> v;
        add(u,v);
        add(v,u);
    }
    
    dfs1(1,0,1);
    dfs2(1,1);
    
    build(1,1,n);
    
    int q;
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op==1)
        {
            int u,v,k;
            cin >> u >> v >> k;
            modify_path(u,v,k);
        }
        else if (op==2)
        {
            int u,k;
            cin >> u >> k;
            modify_tree(u,k);
        }
        else if (op==3)
        {
            int u,v;
            cin >> u >> v;
            cout << query_path(u,v) << "\n";
        }
        else
        {
            int u;
            cin >> u;
            cout << query_tree(u) << "\n";
        }
    }
    
    return 0;
}
    Splay 
    struct node
{
    int v,p,s[2];
    int sz;
    
    void init(int tv,int tp)
    {
        v=tv,p=tp;
        sz=1;
    }
} tr[N];
int root,idx;

void pushup(int u)
{
    tr[u].sz=tr[tr[u].s[0]].sz+tr[tr[u].s[1]].sz+1;
}

void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=(tr[y].s[1]==x);
    tr[z].s[(tr[z].s[1]==y)]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}

void splay(int x,int k)
{
    while (tr[x].p!=k)
    {
        int y=tr[x].p,z=tr[y].p;
        if (z!=k)
        {
            if ((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) root=x;
}

void Insert(int v)
{
    int u=root,p=0;
    while (u) 
    {
        p=u;
        u=tr[u].s[v>tr[u].v];
    }
    u=++idx;
    if (p) tr[p].s[v>tr[p].v]=u;
    tr[u].init(v,p);
    splay(u,0);
}

int get_rank(int v)
{
    int u=root;
    int rk=0;
    while (u)
    {
        if (tr[u].v<v) 
        {
            rk+=tr[tr[u].s[0]].sz+1;
            u=tr[u].s[1];
        }
        else u=tr[u].s[0];
    }
    return rk;
}

void Delete(int v)
{
    int u=root;
    while (u)
    {
        if (tr[u].v==v) break;
        if (tr[u].v<v) u=tr[u].s[1];
        else u=tr[u].s[0];
    }
    splay(u,0);
    int l=tr[u].s[0],r=tr[u].s[1];
    while (tr[l].s[1]) l=tr[l].s[1];
    while (tr[r].s[0]) r=tr[r].s[0];
    splay(l,0),splay(r,l);
    tr[r].s[0]=0;
    pushup(r),pushup(l);
}

int get_pre(int v)
{
    int u=root,res=-INF;
    while (u)
    {
        if (tr[u].v<v) 
        {
            res=max(res,tr[u].v);
            u=tr[u].s[1];
        }
        else u=tr[u].s[0];
    }
    return res;
}

int get_next(int v)
{
    int u=root,res=INF;
    while (u)
    {
        if (tr[u].v>v)
        {
            res=min(res,tr[u].v);
            u=tr[u].s[0];
        }
        else u=tr[u].s[1];
    }
    return res;
}
    线段树合并 
    int merge(int &p,int &q,int l,int r)
{
	if (!p || !q) return p^q;
	if (l==r)
	{
  	/**/
		return p;
	}
	int mid=l+(r-l)/2;
	tr[p].lc=merge(tr[p].lc,tr[q].lc,l,mid);
	tr[p].rc=merge(tr[p].rc,tr[q].rc,mid+1,r);
	pushup(p);
	return p;
}
    AC自动机 
    int son[N][26],cnt[N],idx; //Trie
int q[N]; //队列
int ne[N]; //AC自动机

void Insert(string s)
{
    int u=0;
    for (int i=0;i<s.length();i++)
    {
        int ch=s[i]-'a';
        if (!son[u][ch]) son[u][ch]=++idx;
        u=son[u][ch];
    }
    cnt[u]++;
}

void build() //建立AC自动机
{
    int hh=0,tt=-1;
    for (int i=0;i<26;i++)
    {
        if (son[0][i])
        {
            q[++tt]=son[0][i];
        }
    }
    while (hh<=tt)
    {
        int u=q[hh++];
        for (int i=0;i<26;i++)
        {
            int v=son[u][i];
            if (!v) son[u][i]=son[ne[u]][i];
            else
            {
                ne[v]=son[ne[u]][i];
                q[++tt]=v;
            }
        }
    }
}
    莫队 
    #include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=50010,M=200010,C=1000010;
int n,m;
int c[N];

int B;
int get(int x) { return x/B; }
struct Query
{
    int l,r,id;
    friend bool operator < (const Query lhs,const Query rhs) 
    {
    	int p=get(lhs.l),q=get(rhs.l);
    	if (p!=q) return p<q;
    	return (p&1) ? lhs.r<rhs.r : lhs.r>rhs.r;
    }
} q[M];
int ans[M];
int cnt[C];

void add(int col,int &res)
{
    if (!cnt[col]) res++;
    cnt[col]++;
}

void del(int col,int &res)
{
    if (cnt[col]==1) res--;
    cnt[col]--;
}

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> c[i];
    cin >> m;
    
    for (int i=1;i<=m;i++)
    {
        int l,r;
        cin >> l >> r;
        q[i]={l,r,i};
    }
    
    B=sqrt(n);
    sort(q+1,q+m+1);
    
    for (int k=1,i=0,j=1,res=0;k<=m;k++)
    {
        int l=q[k].l,r=q[k].r;
        while (i<r) add(c[++i],res);
        while (j>l) add(c[--j],res);
        while (i>r) del(c[i--],res);
        while (j<l) del(c[j++],res);
        
        ans[q[k].id]=res;
    }
    for (int i=1;i<=m;i++) cout << ans[i] << "\n";
    
    return 0;
}
    BSGS 
    #include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long ll;

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

int BSGS(int a,int b,int p)
{
    if (1%p==b%p) return 0;
    int k=sqrt(p)+1;
    unordered_map<int,int> mp;
    int t=b%p;
    for (int i=0;i<k;i++)
    {
        // b*a^i%p
        mp[t]=i;
        t=(ll)t*a%p;
    }
    int ak=qmi(a,k,p);
    t=ak;
    for (int i=1;i<=k;i++)
    {
        // a^(ki)
        if (mp.count(t)) return i*k-mp[t];
        t=(ll)t*ak%p;
    }
    return -1;
}

int main()
{
    int a,b,p;
    cin >> p >> a >> b;

    int res=BSGS(a,b,p);
    if (res==-1) puts("no solution");
    else cout << res << "\n";
    
    return 0;
}
    线性基 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N=60;
int n;
ll p[N];
 
void Insert(ll x)
{
	for (int i=50;i>=0;i--)
	{
		if ((x>>i)&1)
		{
			if (!p[i]) 
			{
				p[i]=x;
				return;
			}
			else x^=p[i];
		}
	}
}

ll get_max()
{
	ll res=0;
	for (int i=50;i>=0;i--) res=max(res,res^p[i]);
	return res;
}
 
int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
	{
		ll x;
		cin >> x;
		Insert(x);
	}
	
	cout << get_max() << "\n";
	
	return 0;
}
    树套树
    线段树套平衡树 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=2000010,INF=1e8+10;
int n,m;
int w[N];
struct node
{
    int v,p,s[2];
    int sz;
    
    void init(int tv,int tp)
    {
        v=tv,p=tp;
        sz=1;
    }
} tr[N];
int idx;

void pushup(int u)
{
    tr[u].sz=tr[tr[u].s[0]].sz+tr[tr[u].s[1]].sz+1;
}

void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=(tr[y].s[1]==x);
    tr[z].s[(tr[z].s[1]==y)]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}

void splay(int &root,int x,int k)
{
    while (tr[x].p!=k)
    {
        int y=tr[x].p,z=tr[y].p;
        if (z!=k)
        {
            if ((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) root=x;
}

void Insert(int &root,int v)
{
    int u=root,p=0;
    while (u) 
    {
        p=u;
        u=tr[u].s[v>tr[u].v];
    }
    u=++idx;
    if (p) tr[p].s[v>tr[p].v]=u;
    tr[u].init(v,p);
    splay(root,u,0);
}

int get_rank(int root,int v)
{
    int u=root;
    int rk=0;
    while (u)
    {
        if (tr[u].v<v) 
        {
            rk+=tr[tr[u].s[0]].sz+1;
            u=tr[u].s[1];
        }
        else u=tr[u].s[0];
    }
    return rk;
}

void Delete(int &root,int v)
{
    int u=root;
    while (u)
    {
        if (tr[u].v==v) break;
        if (tr[u].v<v) u=tr[u].s[1];
        else u=tr[u].s[0];
    }
    splay(root,u,0);
    int l=tr[u].s[0],r=tr[u].s[1];
    while (tr[l].s[1]) l=tr[l].s[1];
    while (tr[r].s[0]) r=tr[r].s[0];
    splay(root,l,0),splay(root,r,l);
    tr[r].s[0]=0;
    pushup(r),pushup(l);
}

void change(int &root,int v1,int v2)
{
    Delete(root,v1);
    Insert(root,v2);
}

int get_pre(int root,int v)
{
    int u=root,res=-INF;
    while (u)
    {
        if (tr[u].v<v) 
        {
            res=max(res,tr[u].v);
            u=tr[u].s[1];
        }
        else u=tr[u].s[0];
    }
    return res;
}

int get_next(int root,int v)
{
    int u=root,res=INF;
    while (u)
    {
        if (tr[u].v>v)
        {
            res=min(res,tr[u].v);
            u=tr[u].s[0];
        }
        else u=tr[u].s[1];
    }
    return res;
}

struct Node
{
    int l,r;
    int rt;
} Tr[N];

void build(int u,int l,int r)
{
    Tr[u].l=l,Tr[u].r=r;
    Insert(Tr[u].rt,INF),Insert(Tr[u].rt,-INF);
    for (int i=l;i<=r;i++) Insert(Tr[u].rt,w[i]);
    if (l==r) return;
    int mid=l+(r-l)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}

void modify(int u,int x,int v)
{
    change(Tr[u].rt,w[x],v);
    if (Tr[u].l==Tr[u].r) return;
    int mid=Tr[u].l+(Tr[u].r-Tr[u].l)/2;
    if (x<=mid) modify(u*2,x,v);
    else modify(u*2+1,x,v);
}

int query_cnt(int u,int l,int r,int x)
{
    if (l<=Tr[u].l && Tr[u].r<=r) return get_rank(Tr[u].rt,x)-1;
    int mid=Tr[u].l+(Tr[u].r-Tr[u].l)/2;
    int res=0;
    if (l<=mid) res+=query_cnt(u*2,l,r,x);
    if (r>mid) res+=query_cnt(u*2+1,l,r,x);
    return res;
}

int query_pre(int u,int l,int r,int x)
{
    if (l<=Tr[u].l && Tr[u].r<=r) return get_pre(Tr[u].rt,x);
    int mid=Tr[u].l+(Tr[u].r-Tr[u].l)/2;
    int res=-INF;
    if (l<=mid) res=max(res,query_pre(u*2,l,r,x));
    if (r>mid) res=max(res,query_pre(u*2+1,l,r,x));
    return res;
}

int query_next(int u,int l,int r,int x)
{
    if (l<=Tr[u].l && Tr[u].r<=r) return get_next(Tr[u].rt,x);
    int mid=Tr[u].l+(Tr[u].r-Tr[u].l)/2;
    int res=INF;
    if (l<=mid) res=min(res,query_next(u*2,l,r,x));
    if (r>mid) res=min(res,query_next(u*2+1,l,r,x));
    return res;
}

int main()
{   
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> w[i];
    
    build(1,1,n);
    
    while (m--)
    {
        int op;
        cin >> op;
        if (op==1)
        {
            int L,R,x;
            cin >> L >> R >> x;
            int res=query_cnt(1,L,R,x)+1;
            cout << res << "\n";
        }
        else if (op==2)
        {
            int L,R,k;
            cin >> L >> R >> k;
        
			int l=-1,r=INF;
			int res;
			while (l<=r)
			{
				int mid=l+(r-l)/2;
				if (query_cnt(1,L,R,mid)+1<=k)
				{
					res=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			cout << res << "\n";
        }
        else if (op==3)
        {
            int pos,x;
            cin >> pos >> x;
            modify(1,pos,x);
            w[pos]=x;
        }
        else if (op==4)
        {
            int L,R,x;
            cin >> L >> R >> x;
            int res=query_pre(1,L,R,x);
            
            if (res==-INF) puts("-2147483647");
            else cout << res << "\n";
        }
        else
        {
            int L,R,x;
            cin >> L >> R >> x;
            int res=query_next(1,L,R,x);
            
            if (res==INF) puts("2147483647");
            else cout << res << "\n";
        }
    }
    
    return 0;
}
    线段树套线段树 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=50010,M=50010,MLOG2N=M*17*17,V=4*N;
typedef long long ll;
int n,m;
struct node
{
    int lc,rc;
    ll sum,add;
    #define lc(u) (tr[u].lc ? tr[u].lc : tr[u].lc=++idx)
    #define rc(u) (tr[u].rc ? tr[u].rc : tr[u].rc=++idx)
} tr[MLOG2N]; //内层下标上的线段树
int idx;
struct Node
{
    int l,r;
    int rt;
} Tr[V]; //外层权值线段树

struct Query
{
    int op,l,r;
	ll c;
} q[M];
ll t[M];
int tlen;
int get(ll x)
{
    return lower_bound(t+1,t+tlen+1,x)-t;
}

void pushup(int u)
{
    tr[u].sum=tr[lc(u)].sum+tr[rc(u)].sum;
}

void pushdown(int u,int l,int r)
{
    node &root=tr[u],&left=tr[lc(u)],&right=tr[rc(u)];
    int mid=l+(r-l)/2;
    int ll=l,lr=mid,rl=mid+1,rr=r;
    if (root.add)
    {
        left.sum+=1ll*(lr-ll+1)*root.add;
        left.add+=root.add;
        
        right.sum+=1ll*(rr-rl+1)*root.add;
        right.add+=root.add;
        
        root.add=0;
    }
}

void modify(int u,int l,int r,int ql,int qr)
{
    if (ql<=l && r<=qr) 
    {
        tr[u].sum+=r-l+1;
        tr[u].add++;
        return;
    }
    pushdown(u,l,r);
    int mid=l+(r-l)/2;
    if (ql<=mid) modify(lc(u),l,mid,ql,qr);
    if (qr>mid) modify(rc(u),mid+1,r,ql,qr);
    pushup(u);
}

ll query(int u,int l,int r,int ql,int qr)
{
    if (ql<=l && r<=qr) return tr[u].sum;
    pushdown(u,l,r);
    int mid=l+(r-l)/2;
    ll res=0;
    if (ql<=mid) res+=query(lc(u),l,mid,ql,qr);
    if (qr>mid) res+=query(rc(u),mid+1,r,ql,qr);
    return res;
}

void build(int u,int l,int r) //建立外层权值线段树
{
    Tr[u].l=l,Tr[u].r=r,Tr[u].rt=++idx;
    if (l==r) return;
    int mid=l+(r-l)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}

void update(int u,int l,int r,int c) //将下标在[l,r]区间中且值域范围包含了c的区间更新
{
    modify(Tr[u].rt,1,n,l,r);
    if (Tr[u].l==Tr[u].r) return;
    int mid=Tr[u].l+(Tr[u].r-Tr[u].l)/2;
    if (c<=mid) update(u*2,l,r,c);
    else update(u*2+1,l,r,c);
}

ll GetValByRank(int u,int l,int r,ll c) 
{
    if (Tr[u].l==Tr[u].r) return t[Tr[u].l];
    ll k=query(Tr[u*2+1].rt,1,n,l,r); //右儿子中下标在[l,r]区间中的数的个数
    if (k>=c) return GetValByRank(u*2+1,l,r,c);
    else return GetValByRank(u*2,l,r,c-k);
}

int main()
{
    cin >> n >> m;
    
    for (int i=1;i<=m;i++)
    {
        int op,l,r;
		ll c;
        cin >> op >> l >> r >> c;
        q[i]={op,l,r,c};
        if (op==1) t[++tlen]=c;
    }
    
    sort(t+1,t+tlen+1);
    tlen=unique(t+1,t+tlen+1)-t-1;
    
    build(1,1,tlen);
    
    for (int i=1;i<=m;i++)
    {
        int op=q[i].op,l=q[i].l,r=q[i].r;
		ll c=q[i].c;
        if (op==1) update(1,l,r,get(c));
        else cout << GetValByRank(1,l,r,c) << "\n";
    }
    
    return 0;
}
    凸包 
    #include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef pair<double,double> Point;
typedef Point Vector;
#define x first
#define y second

Vector operator - (Vector a,Vector b) { return {a.x-b.x,a.y-b.y}; }
double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
double area(Point a,Point b,Point c) { return cross(b-a,c-a); }
double get_dist(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

const int N=100010;
int n;
Point p[N];

int stk[N],top;
bool used[N];

void Convex_Hull()
{
	sort(p+1,p+n+1);
	n=unique(p+1,p+n+1)-p-1;
	
	top=0;
	for (int i=1;i<=n;i++)
	{
		while (top>1 && area(p[stk[top-1]],p[stk[top]],p[i])<0) used[stk[top--]]=false;
		stk[++top]=i;
		used[i]=true;
	}	
	used[1]=false;
	for (int i=n;i>=1;i--)
	{
		if (used[i]) continue;
		while (top>1 && area(p[stk[top-1]],p[stk[top]],p[i])<0) used[stk[top--]]=false;
		stk[++top]=i;
	}
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++) cin >> p[i].x >> p[i].y;
	
	Convex_Hull();
	
	double ans=0;
	for (int i=1;i<top;i++) ans+=get_dist(p[stk[i]],p[stk[i+1]]);
	printf("%.2lf",ans);
		
    return 0;
}
    旋转卡壳 
    #include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef pair<int,int> Point;
typedef Point Vector;
#define x first
#define y second

Vector operator - (Vector a,Vector b) { return {a.x-b.x,a.y-b.y}; }
int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
int area(Point a,Point b,Point c) { return cross(b-a,c-a); }
int get_dist(Point a,Point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); }

const int N=50010;
int n;
Point p[N];

int stk[N],top;
bool used[N];

void Convex_Hull()
{
	sort(p+1,p+n+1);
	n=unique(p+1,p+n+1)-p-1;
	
	top=0;
	for (int i=1;i<=n;i++)
	{
		while (top>1 && area(p[stk[top-1]],p[stk[top]],p[i])<=0) 
		{
			if (area(p[stk[top-1]],p[stk[top]],p[i])<0) used[stk[top]]=false;
			top--;
		}
		stk[++top]=i;
		used[i]=true;
	}	
	used[1]=false;
	for (int i=n;i>=1;i--)
	{
		if (used[i]) continue;
		while (top>1 && area(p[stk[top-1]],p[stk[top]],p[i])<=0) used[stk[top--]]=false;
		stk[++top]=i;
		used[i]=true;
	}
	top--;
}

#define nxt(x) (x==top ? 1 : x+1)

int rotating_calipers()
{
	if (top<=2) return get_dist(p[1],p[n]);
	
	int res=0;
	for (int i=1,j=3;i<=top;i++)
	{
		Point a=p[stk[i]],b=p[stk[nxt(i)]];
		while (area(a,b,p[stk[j]])<area(a,b,p[stk[nxt(j)]])) j=nxt(j);
		Point c=p[stk[j]];
		res=max(res,max(get_dist(a,c),get_dist(b,c)));
	}
	return res;
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++) cin >> p[i].x >> p[i].y;
	
	Convex_Hull();
	//for (int i=1;i<=top;i++) cout << p[stk[i]].x << " " << p[stk[i]].y << "\n";
	
	printf("%d",rotating_calipers());
		
    return 0;
}
    多项式模板 
    
namespace Poly
{
	typedef vector<int> poly;
	const int mod=998244353,G=3,niG=332748118;
	int bit,tot,rev[N];
	
	void print(poly a)
	{
		for (int i=0;i<a.size();i++) cout << a[i] << " ";
		cout << "\n";
	}
	
	void NTT(poly &a,int dir)
	{
		for (int i=0;i<tot;i++)
		{
			if (i<rev[i])
			{
				swap(a[i],a[rev[i]]);
			}
		}
		for (int mid=1;mid<tot;mid<<=1)
		{
			int wn1=qmi((dir==1 ? G : niG),(mod-1)/(mid<<1),mod);
			for (int i=0;i<tot;i+=(mid<<1))
			{
				int wnk=1;
				for (int j=0;j<mid;j++,wnk=(ll)wnk*wn1%mod)
				{
					int x=a[i+j],y=(ll)wnk*a[i+j+mid]%mod;
					a[i+j]=(x+y)%mod;
					a[i+j+mid]=((ll)x-y+mod)%mod;
				}
			}
		}
	}
	
	void DFT(poly &a) 
	{
		NTT(a,1);
	}
	
	void IDFT(poly &a)
	{
		NTT(a,-1);
		int nitot=qmi(tot,mod-2,mod);
		for (int i=0;i<a.size();i++) a[i]=(ll)a[i]*nitot%mod;
	}
	
	poly operator + (poly a,poly b)
	{
		int len=max(a.size(),b.size());
		a.resize(len),b.resize(len);
		for (int i=0;i<len;i++) a[i]=(a[i]+b[i])%mod;
		return a;
	}
	
	poly operator - (poly a,poly b)
	{
		int len=max(a.size(),b.size());
		a.resize(len),b.resize(len);
		for (int i=0;i<len;i++) a[i]=((ll)a[i]-b[i]+mod)%mod;
		return a;
	}
	
	poly operator * (poly a,int b)
	{
		for (int i=0;i<a.size();i++) a[i]=(ll)a[i]*b%mod;
		return a;
	}
	
	poly operator * (poly a,poly b)
	{
		int n=a.size()-1,m=b.size()-1;
		bit=0;
		while ((1<<bit)<n+m+1) bit++;
		tot=(1<<bit);
		for (int i=0;i<tot;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		
		a.resize(tot),b.resize(tot);
		
		DFT(a),DFT(b);
		for (int i=0;i<tot;i++) a[i]=(ll)a[i]*b[i]%mod;
		IDFT(a);
		
		a.resize(n+m+1);
		
		return a;
	}
	
	poly Inv(poly F,int n)
	{
		poly G2,G;
		G2.resize(1);
		G2[0]=qmi(F[0],mod-2,mod);
		for (int k=2;;k<<=1)
		{
			// mod x^k
			// G(x)=2G2(x)-F(x)G2(x)G2(x) (mod x^n)
			
			poly t1=G2*G2,t2=F;
			t1.resize(k),t2.resize(k);
			poly t=t1*t2;
			t.resize(k);
			G=G2*2-t;
			G.resize(k);
			G2=G;
			if (k>=n) break;
		}
		G.resize(n+1);
		
		return G;
	}
};
    FWT 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=(1<<18)|1,mod=998244353,ni2=499122177;
typedef long long ll; 
int n;
int A[N],B[N];
int a[N],b[N];

int Mod(int x)
{
	if (x>=mod) x-=mod;
	if (x<0) x+=mod;
	return x;
}

void adm(int &x,int y)
{
	x+=y;
	x=Mod(x);
}

void copy()
{
	for (int i=0;i<(1<<n);i++) 
	{
		a[i]=A[i];
		b[i]=B[i];	
	}
}

void mul()
{
	for (int i=0;i<(1<<n);i++) a[i]=(ll)a[i]*b[i]%mod;
}

void print()
{
	for (int i=0;i<(1<<n);i++) cout << a[i] << " ";
	cout << "\n";
}

void OR(int f[],int dir)
{
	for (int mid=1;mid<(1<<n);mid<<=1)
	{
		for (int i=0;i<(1<<n);i+=(mid<<1))
		{
			for (int j=0;j<mid;j++)
			{
				adm(f[i+j+mid],Mod(f[i+j]*dir));
			}
		}
	}
}

void AND(int f[],int dir)
{
	for (int mid=1;mid<(1<<n);mid<<=1)
	{
		for (int i=0;i<(1<<n);i+=(mid<<1))
		{
			for (int j=0;j<mid;j++)
			{
				adm(f[i+j],Mod(f[i+j+mid]*dir));
			}
		}
	}
}

void XOR(int f[],int dir)
{
	for (int mid=1;mid<(1<<n);mid<<=1)
	{
		for (int i=0;i<(1<<n);i+=(mid<<1))
		{
			for (int j=0;j<mid;j++)
			{
				int t=f[i+j];
				adm(f[i+j],f[i+j+mid]);
				f[i+j+mid]=Mod(t-f[i+j+mid]);
				f[i+j]=(ll)f[i+j]*dir%mod;
				f[i+j+mid]=(ll)f[i+j+mid]*dir%mod;
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i=0;i<(1<<n);i++) cin >> A[i];
	for (int i=0;i<(1<<n);i++) cin >> B[i];
	
	copy(),OR(a,1),OR(b,1),mul(),OR(a,-1),print();
	copy(),AND(a,1),AND(b,1),mul(),AND(a,-1),print();
	copy(),XOR(a,1),XOR(b,1),mul(),XOR(a,ni2),print();
	
	return 0;
}
    FHQ-Treap 
    #include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N=100010;
int n,m;
int val[N],pri[N],ch[N][2],sz[N],rev[N],idx,root;

int new_node(int v)
{
	++idx;
	val[idx]=v;
	pri[idx]=rand();
	sz[idx]=1;
	return idx;
}

void pushup(int u)
{
	sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
}

void Rev(int u)
{
	swap(ch[u][0],ch[u][1]);
	rev[u]^=1;
}

void pushdown(int u)
{
	if (rev[u])
	{
		Rev(ch[u][0]);
		Rev(ch[u][1]);
		rev[u]=0;
	}
}

void split(int rt,int k,int &rt1,int &rt2)
{
	if (!rt)
	{
		rt1=rt2=0;
		return;
	}
	pushdown(rt);
	if (sz[ch[rt][0]]+1<=k)
	{
		rt1=rt;
		split(ch[rt][1],k-sz[ch[rt][0]]-1,ch[rt][1],rt2);
	}
	else
	{
		rt2=rt;
		split(ch[rt][0],k,rt1,ch[rt][0]);
	}
	pushup(rt);
}

int merge(int rt1,int rt2)
{
	if (!rt1 || !rt2) return rt1^rt2;
	if (pri[rt1]<pri[rt2])
	{
		pushdown(rt1);
		ch[rt1][1]=merge(ch[rt1][1],rt2);
		pushup(rt1);
		return rt1;
	}
	else
	{
		pushdown(rt2);
		ch[rt2][0]=merge(rt1,ch[rt2][0]);
		pushup(rt2);
		return rt2;
	}
}

void Insert(int v)
{
	root=merge(root,new_node(v));
}

void print(int u)
{
	pushdown(u);
	if (ch[u][0]) print(ch[u][0]);
	cout << val[u] << " ";
	if (ch[u][1]) print(ch[u][1]);
}

int main()
{
	srand(time(0));
	
	int n,m;
	cin >> n >> m;
	for (int i=1;i<=n;i++) Insert(i);
	
	while (m--)
	{
		int l,r;
		cin >> l >> r;
		int x,y,z;
		split(root,r,y,z);
		split(y,l-1,x,y);
		Rev(y);
		root=merge(merge(x,y),z);
	}
	
	print(root);
	
	return 0;
}
    后缀数组SA 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1000010;
int n;
string s;
int sa[N],rk[N],prk[N];
int height[N];

void get_SA()
{
	for (int i=1;i<=n;i++)
	{
		sa[i]=i;
		rk[i]=s[i];
	}
	for (int k=1;k<=n;k<<=1)
	{
		sort(sa+1,sa+n+1,[&](int x,int y)
		{
			if (rk[x]!=rk[y]) return rk[x]<rk[y];
			return rk[x+k]<rk[y+k];
		});
		for (int i=1;i<=n;i++) prk[i]=rk[i];
		for (int i=1,num=0;i<=n;i++) rk[sa[i]]=(prk[sa[i]]==prk[sa[i-1]] && prk[sa[i]+k]==prk[sa[i-1]+k]) ? num : ++num;
	}
}

void get_height()
{
	for (int i=1,k=0;i<=n;i++)
	{
		if (rk[i]==1) continue;
		if (k) k--;
		int j=sa[rk[i]-1];
		while (i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
		height[rk[i]]=k;
	}
}

int main()
{
	cin >> s;
	n=s.length();
	s=" "+s;
	
	get_SA();
	get_height();
	
	for (int i=1;i<=n;i++) printf("%d ",sa[i]);
	puts("");
	for (int i=1;i<=n;i++) printf("%d ",height[i]);
	puts("");
	
	return 0;
}
    最大流Dinic 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=10010,M=200010;
const int INF=1e9;
int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N];
int cur[N]; 

void add(int u,int v,int c)
{
    e[idx]=v,f[idx]=c,ne[idx]=h[u],h[u]=idx++;
    e[idx]=u,f[idx]=0,ne[idx]=h[v],h[v]=idx++;
}

bool bfs()
{
    memset(d,-1,sizeof(d));
    int hh=0,tt=-1;
    q[++tt]=S;
    d[S]=0;
    cur[S]=h[S];
    while (hh<=tt)
    {
        int u=q[hh++];
        for (int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if (d[v]==-1 && f[i]>0)
            {
                d[v]=d[u]+1;
                cur[v]=h[v];
                if (v==T) return true;
                q[++tt]=v;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if (u==T) return limit;
    int flow=0;
    for (int i=cur[u];i!=-1 && flow<limit;i=ne[i]) //满足没有达到流量上限
    {
        cur[u]=i; //当前弧优化
        int v=e[i];
        if (d[v]==d[u]+1 && f[i]>0)
        {
            int t=find(v,min(f[i],limit-flow));
            if (!t) d[v]=-1; //无法增广的标记不可用
            f[i]-=t,f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while (bfs()) while (flow=find(S,INF)) maxflow+=flow;
    return maxflow;
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=m;i++)
    {
        int u,v,c;
        cin >> u >> v >> c;
        add(u,v,c);
    }
    
    cout << dinic() << "\n";
    
    return 0;
}
    费用流EK 
    #include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=5010,M=100010;
const int INF=1e9;
int n,m,S,T;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],pre[N],incf[N];
bool vis[N];

void add(int u,int v,int c,int cost)
{
    e[idx]=v,f[idx]=c,w[idx]=cost,ne[idx]=h[u],h[u]=idx++;
    e[idx]=u,f[idx]=0,w[idx]=-cost,ne[idx]=h[v],h[v]=idx++;
}

bool spfa()
{
    memset(d,0x3f,sizeof(d));
    memset(incf,0,sizeof(incf));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    d[S]=0;
    incf[S]=INF;
    q.push(S);
    
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for (int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if (f[i]>0 && d[v]>d[u]+w[i])
            {
                d[v]=d[u]+w[i];
                pre[v]=i;
                incf[v]=min(incf[u],f[i]);
                if (!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return (incf[T]>0);
}

void EK_mcmf(int &flow,int &cost)
{
    flow=0;
    cost=0;
    while (spfa())
    {
        int t=incf[T];
        flow+=t,cost+=d[T]*t;
        for (int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=m;i++)
    {
        int u,v,c,cost;
        cin >> u >> v >> c >> cost;
        add(u,v,c,cost);
    }
    
    int flow,cost;
    EK_mcmf(flow,cost);
    cout << flow << " " << cost << "\n";
    
    return 0;
}
    CDQ分治 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=100010,M=200010;
int n,m;
int ans[N];
struct Data { int a,b,c,cnt,res; } dat[N];
bool operator < (Data p,Data q)
{
    if (p.a!=q.a) return p.a<q.a;
    if (p.b!=q.b) return p.b<q.b;
    return p.c<q.c;
}
bool operator == (Data p,Data q) { return (p.a==q.a) && (p.b==q.b) && (p.c==q.c); }

int tr[M];
inline int lowbit(int x) { return x & (-x); }
inline void add(int x,int v) { for (;x<=m;x+=lowbit(x)) tr[x]+=v; }
inline int query(int x) 
{
    int res=0;
    for (;x;x-=lowbit(x)) res+=tr[x];
    return res;
}

Data t[N];

void solve(int l,int r)
{
    if (l>=r) return;
    int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r);
    int i=l,j=mid+1,k=0;
    while (i<=mid && j<=r)
    {
        if (dat[i].b<=dat[j].b) 
        {
            add(dat[i].c,dat[i].cnt);
            t[++k]=dat[i++];
        }
        else 
        {
            dat[j].res+=query(dat[j].c);
            t[++k]=dat[j++];
        }
    }
    while (i<=mid) 
    {
        add(dat[i].c,dat[i].cnt);
        t[++k]=dat[i++];
    }
    while (j<=r)
    {
        dat[j].res+=query(dat[j].c);
        t[++k]=dat[j++];
    }
    for (int i=l;i<=mid;i++) add(dat[i].c,-dat[i].cnt);
    for (int i=l,k=1;i<=r;i++,k++) dat[i]=t[k];
}

int main()
{
    cin >> n >> m;
    for (int i=1;i<=n;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        dat[i]={a,b,c,1,0};
    }
    
    sort(dat+1,dat+n+1);
    
    int k=0;
    for (int i=1;i<=n;i++) 
    {
        if (k && dat[i]==dat[k]) dat[k].cnt++;
        else dat[++k]=dat[i];
    }
    
    solve(1,k);
    
    for (int i=1;i<=k;i++) 
    {
        int res=dat[i].res+dat[i].cnt-1;
        ans[res]+=dat[i].cnt;
    }
    
    for (int i=0;i<n;i++) cout << ans[i] << "\n";
    
    return 0;
}
    李超树 
    namespace Convex_Hull
{
	struct line
	{
		ll k,b;
		line(ll _k=0,ll _b=1e18) { k=_k,b=_b; }
		ll val(ll x) { return k*x+b; }
	} tr[N]; 
	int lc[N],rc[N];
	int rt,idx;
	
	void ins(int &u,int l,int r,line p)
	{
		if (!u) u=++idx;
		int mid=(l+r)>>1;
		if (tr[u].val(mid)>p.val(mid)) swap(tr[u],p);
		if (p.val(l)<tr[u].val(l)) ins(lc[u],l,mid,p);
		if (p.val(r)<tr[u].val(r)) ins(rc[u],mid+1,r,p);
	}
	
	ll qry(int &u,int l,int r,int x)
	{
		if (!u || l>x || r<x) return 1e18;
		int mid=(l+r)>>1;
		ll res=tr[u].val(x);
		res=min(res,qry(lc[u],l,mid,x));
		res=min(res,qry(rc[u],mid+1,r,x));
		return res;
	}
	
	void Ins(line p) { ins(rt,0,1e6,p); }
	
	ll Qry(int x) { return qry(rt,0,1e6,x); }
}
    后缀自动机SAM 
    int tot=1,lst=1;
struct Node
{
	int len,fa;
	int ch[26];
} node[N];

void extend(int c)
{
	int p=lst,np=lst=++tot;
	node[np].len=node[p].len+1;
	for (;p && !node[p].ch[c];p=node[p].fa) node[p].ch[c]=np;
	if (!p) node[np].fa=1;
	else 
	{
		int q=node[p].ch[c];
		if (node[q].len==node[p].len+1) node[np].fa=q;
		else
		{
			int nq=++tot;
			node[nq]=node[q],node[nq].len=node[p].len+1;
			node[q].fa=node[np].fa=nq;
			for (;p && node[p].ch[c]==q;p=node[p].fa) node[p].ch[c]=nq;
		}
	}
}
    Manacher 
    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=20000010;
int n;
string s;
int p[N];

void init()
{
	string t="$#";
	for (int i=0;i<n;i++) 
	{
		t+=s[i];
		t+='#';
	}
	t+='^';
	s=t;n=s.length();
}

void Manacher()
{
	int r=0,mid;
	for (int i=1;i<n;i++)
	{
		if (i<r) p[i]=min(p[2*mid-i],r-i);
		else p[i]=1;
		while (s[i-p[i]]==s[i+p[i]]) p[i]++;
		if (i+p[i]>r) { r=i+p[i],mid=i; }
	}
}

int main()
{
	cin >> s;
	n=s.length();
	init();
	
	Manacher();
	
	int ans=0;
	for (int i=0;i<n;i++) ans=max(ans,p[i]);
	cout << ans-1 << "\n";
	
	return 0;
}
    Modint 
    typedef long long ll;
const int mod=1e9+7;
struct mint
{
	int x;
	mint() { x=0; }
	mint(int y) { x=(y<0) ? (y+mod) : ((y>=mod) ? y-mod : y); }
	friend ostream &operator << (ostream &os,const mint &p) { return os << p.x; }
	friend istream &operator >> (istream &is,mint &p) 
	{
		int x;is >> x;p=mint(x);
		return is;
	}
	friend mint operator + (const mint &lhs,const mint &rhs) { return mint(lhs.x+rhs.x); }
	friend mint operator - (const mint &lhs,const mint &rhs) { return mint(lhs.x-rhs.x); }
	friend mint operator * (const mint &lhs,const mint &rhs) { return mint((ll)lhs.x*rhs.x%mod); }
	friend mint operator ^ (mint a,int b) 
	{
		mint res(1);
		while (b)
		{
			if (b&1) res=res*a;
			a=a*a;
			b>>=1;
		}
		return res;
	}
	friend mint inv(const mint &p) { return p^(mod-2); }
	friend mint operator / (const mint &lhs,const mint &rhs) { return lhs*inv(rhs); } 
	mint &operator += (const mint &o) { return (*this)=(*this)+o; }
	mint &operator -= (const mint &o) { return (*this)=(*this)-o; }
	mint &operator *= (const mint &o) { return (*this)=(*this)*o; }
	mint &operator /= (const mint &o) { return (*this)=(*this)/o; }
};
    杂项
    火车头 
    //2022tysc1772
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fdelete-null-pointer-checks")
    杂物

    853972641

    正宗信奥牌

    大事年表

    2024年10月14日 蓝70

    2024年10月17日 绿120

    2024年11月21日 蓝100

    2024年12月23日 紫30+黑1+总通过500

    2025年2月26日 蓝180+紫70

    2025年4月25日 蓝200+紫100

    2025年5月5日 黑10

  • 最近活动

  • Stat

  • Rating

779
已递交
516
已通过
0
题解被赞
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 粤ICP备2024335011号
  3. Worker 0, 67ms
  4. Powered by Hydro v4.19.1 Community