事件起源于

全电竞班的唯一的一只蒟蒻——珍稀号LL

去上文化课之后

所以大多由MAXDY_大佬向在下转述

PART 1

陌头驻马，正值朝光

妹子oj一众大佬们疯狂地敲着键盘

只见千行代码，流于指间

嘴中却念念有词互相fake

原因无他

在失去蒟蒻垫底后，大佬们很高兴

终于不用为了安慰蒟蒻，而出一堆sb暴力了

他们要堂堂正正考一盘试来证明自己隐藏多年的oi真实实力

并要求欧阳教

“出，把最难的题拿出来”

PART 2

然鹅，欧阳教失踪了

这究竟是人性的泯灭还是道德的沦丧

欢迎走进本期LL口胡秀

大佬们心里都有了一个暗暗的猜测

PART 3

真相只有一个

因为有人害怕自己收不住力度AK全场

使出了斗转星移大法

将欧阳教困在某个不知名的地方

给予欧阳教更多的时间

出一套那人恰好不会AK的题

用心之险恶啊

令人发指！！！

大佬们心照不宣

一时间机房人人自危

PART 4

欧阳教风尘仆仆地在下课铃打响的前一秒进来了

只见他对着全班同学展现出练习多年的

邪魅一笑

那笑容的意思很是明显

放心，这次考试都是模板题

全员A没问题

PART 5

于是有了现在L·老蒟蒻了·中秋还上课·心碎·L狂补大佬们当日

恰好不AK的题

话说大佬何必为难蒟蒻呢

本是同根生，相煎何太急

什么都不会，LL泪两行

EX1Triangle

description

给定一大小为 n 的有点权树，每次询问一对点(u,v)，问是否能在 u 到 v 的简单

路径上取三个点权（点权范围[1,2 31 -1]），以这三个权值为边长构成一个三角形。

同时还支持单点修改。

input

第一行两个整数 n、q 表示树的点数和操作数

第二行 n 个整数表示 n 个点的点权

以下 n-1 行，每行 2 个整数 a、b，表示 a 是 b 的父亲（以 1 为根的情况下）

以下 q 行，每行 3 个整数 t、a、b

若 t=0，则询问(a,b)

若 t=1，则将点 a 的点权修改为 b

output

对每个询问输出一行表示答案，“Y”表示有解，“N”表示无解。

sample input

5 5

1 2 3 4 5

1 2

2 3

3 4

1 5

0 1 3

0 4 5

1 1 4

0 2 5

0 2 3

sample output

N

Y

Y

N

【数据规模与约定】

30%: n,q<=1000，

100%: n,q<=10^5

 

我建议改个名字叫

暴力与feibonacci的爱恨情仇

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=1e5+5;int n,m,k,hd[maxn],val[maxn];int fa[maxn],deep[maxn];struct node{    int to,nt;}e[maxn<<1]; inline void add_edge(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;    }inline void dfs(int x){    deep[x]=deep[fa[x]]+1;    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==fa[x])continue;        fa[v]=x;        dfs(v);    }}int cnt;vector
        
         a;inline bool check(int x){    if(x>=2&&(ll)a[x-2]+(ll)a[x-1]>a[x])re 1;    if(x<=cnt-2&&(ll)a[x]+(ll)a[x+1]>a[x+2])re 1;    if(x>=1&&x<=cnt-1&&(ll)a[x-1]+(ll)a[x]>a[x+1])re 1;    re 0;}inline bool Get_ans(int x,int y){    a.clear();    cnt=0;    while(2333)    {        if(deep[x]
         
          =50)re 1;        if(x==y)re 0;        x=fa[x];    }    re 0;}int main(){    //freopen("in.txt","r",stdin);    ll x,y,opt;    rd(n),rd(m);     inc(i,1,n)    scanf("%lld",&val[i]);    inc(i,2,n)    {        rd(x),rd(y);        add_edge(x,y);    }    dfs(1);        inc(i,1,m)    {        rd(opt);        rd(x),rd(y);        if(opt==1)            val[x]=y;        else         {                if(Get_ans(x,y)==1)printf("Y\n");            else printf("N\n");        }    }    re 0;}
         
        
       
      

 

这道题的美

只有贪心.堆.结论之神庇佑的人才会看得见

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int n,m,l;struct node{    int t;    ll val;    bool operator<(node a)const    {        re a.val
        
         q1,q2; int main(){    freopen("in.txt","r",stdin);    int x,y;    rd(l),rd(n),rd(m);    inc(i,1,n)    {        rd(x);        q1.push((node){x,x});    }        inc(i,1,l)    {        a[i]=q1.top();        q1.pop();        q1.push((node){a[i].t,a[i].val+a[i].t});    }    inc(i,1,m)    {        rd(x);        q2.push((node){x,x});    }        inc(i,1,l)    {        b[i]=q2.top();        q2.pop();        q2.push((node){b[i].t,b[i].t+b[i].val});    }        ll ans=0;    inc(i,1,l)    {        ans=max(ans,a[i].val+b[l-i+1].val);    }    printf("%lld",ans);    re 0;}
        
       
      

 

大家好，我是练习时长2年半的数据结构大佬 线段树

我的爱好是加减乘除

打响指……

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=(1e5+5)*4;ll n,m;ll ans;ll minn[maxn],maxx[maxn],lazy[maxn],sum[maxn];#define lson rt<<1#define rson rt<<1|1inline void pushup(ll rt){    minn[rt]=min(minn[lson],minn[rson]);    maxx[rt]=max(maxx[lson],maxx[rson]);    sum[rt]=sum[lson]+sum[rson];}inline void build(ll rt,ll l,ll r){    if(l==r)    {        rd(maxx[rt]);        sum[rt]=minn[rt]=maxx[rt];        re ;    }        ll mid=(l+r)>>1;    build(lson,l,mid);    build(rson,mid+1,r);        pushup(rt);}inline void pushdown(ll rt,ll l,ll r,ll mid){    minn[lson]+=lazy[rt];minn[rson]+=lazy[rt];    maxx[lson]+=lazy[rt];maxx[rson]+=lazy[rt];    sum[lson]+=(mid-l+1)*lazy[rt];    sum[rson]+=(r-mid)*lazy[rt];    lazy[lson]+=lazy[rt];    lazy[rson]+=lazy[rt];    lazy[rt]=0;}inline void add(ll rt,ll l,ll r,ll x,ll y,ll z){    if(x<=l&&r<=y)    {        lazy[rt]+=z;        sum[rt]+=z*(r-l+1);        minn[rt]+=z;        maxx[rt]+=z;        re ;    }    ll mid=(l+r)>>1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid)add(lson,l,mid,x,y,z);     if(y> mid)add(rson,mid+1,r,x,y,z);     pushup(rt);}inline void div(ll rt,ll l,ll r,ll x,ll y,ll z){    if(x<=l&&r<=y)    {        ll tmp1=maxx[rt]-maxx[rt]/z,tmp2=minn[rt]-minn[rt]/z;        if(maxx[rt]<0&&maxx[rt]/z*z!=maxx[rt])        ++tmp1;        if(minn[rt]<0&&minn[rt]/z*z!=minn[rt])        ++tmp2;                if(tmp1==tmp2)        {            sum[rt]-=(r-l+1)*tmp1;            lazy[rt]-=tmp1;            maxx[rt]-=tmp1;            minn[rt]-=tmp1;            re ;        }        }    ll mid=(l+r)>>1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid) div(lson,l,mid,x,y,z);    if(y>mid) div(rson,mid+1,r,x,y,z);    pushup(rt);}inline void query_sum(ll rt,ll l,ll r,ll x,ll y){    if(x<=l&&r<=y)    {        ans+=sum[rt];        re ;    }    ll mid=(l+r)>>1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid)query_sum(lson,l,mid,x,y);    if(y>mid)query_sum(rson,mid+1,r,x,y);}inline void query_min(ll rt,ll l,ll r,ll x,ll y){    if(x<=l&&r<=y)    {        if(minn[rt]
        
         >1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid)query_min(lson,l,mid,x,y);    if(y>mid)query_min(rson,mid+1,r,x,y);}int main(){//    freopen("in.txt","r",stdin);    rd(n),rd(m);    build(1,1,n);        ll opt,x,y,z;    inc(i,1,m)    {        rd(opt);        rd(x),rd(y);        ++x,++y;        switch(opt){         case 1:rd(z);add(1,1,n,x,y,z);break;          case 2:rd(z);div(1,1,n,x,y,z);break;          case 3:ans=2147483647;query_min(1,1,n,x,y);printf("%lld\n",ans);break;          case 4:ans=0;query_sum(1,1,n,x,y);printf("%lld\n",ans);break;         }    }    re 0;}