长乐Day？.4

————今天不用markdown公式了，预览和实际效果不太一样

线段树

T1：

比较简单，初始值为0，连建树都省了，维护一个线段树记录下区间 [ l, r ] 是否有雾，如果有该区间值为1，没有为0（当然直接加法也行），修改就很简单了几乎版题，而查询时可以通过二分法分别求出区间左右端点（CF有类似的二分），赛时二分还写挂了。

#include
#define N 100001
using namespace std;
int n,m,tag[N*4],tr[N*4];
void pushdown(int q)
{
    if(tag[q]!=2)
    {
        tag[q*2]=tag[q];
        tr[q*2]=tag[q];
        tag[q*2+1]=tag[q];
        tr[q*2+1]=tag[q];
    }
    tag[q]=2;
    return;
}
int query(int l,int r,int q,int ql,int qr)
{
    if(l<=ql&&qr<=r)
    {
        return tr[q];
    }
    pushdown(q);
    int mid=(ql+qr)/2;
    if(rmid) return query(l,r,q*2+1,mid+1,qr);
    return query(l,r,q*2,ql,mid)|query(l,r,q*2+1,mid+1,qr);
}
void update(int l,int r,int w,int q,int ql,int qr)
{
    if(rqr)
    {
        return;
    }
    if(l<=ql&&qr>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a;
        if(a==1)
        {
            cin>>b>>c;
            update(b,c,1,1,1,n);
        }
        else if(a==2)
        {
            cin>>b>>c;
            update(b,c,0,1,1,n);
        }
        else
        {
            cin>>b;
            if(query(b,b,1,1,n))
            {
                cout<<"0"<<endl;
            }
            else if(!query(1,b,1,1,n)||!query(b,n,1,1,n))
            {
                cout<<"INF"<<endl;
            }
            else
            {
                int l=1,r=b,al,ar;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(!query(mid,b,1,1,n))
                    {
                        al=mid;
                        r=mid-1;
                    }
                    else
                    {
                        l=mid+1; 
                    }
                }
                l=b;
                r=n;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(!query(b,mid,1,1,n))
                    {
                        ar=mid;
                        l=mid+1;
                    }
                    else
                    {
                        r=mid-1; 
                    }
                }
                cout<<ar-al+1<<endl;
            }
        }
    }
    return 0;
}

T2：

踹安苟题，考虑最优情况就是取区间内前三大的数，再考虑最劣情况，就是序列A为斐波那契数列，但由于斐波那契数列 f(45)>10^ 9，且n<=10^ 9，而且再此区间内一定有解，所以就变成维护区间前45大，然后接着就是暴力枚举了。刚开始用vector，很好写，不过也很容易炸，一不小心大红大紫大黑，调起来还麻烦，所以后来又把vector改掉了，我不太能理解TJ的时间复杂度=（为什么不是O(45^3nlogn)，2023/7/19 10:12 upd：又理解了，我傻了。

倍增与LCA

没打，赛时在改以前的题，看样子挺难的，明天再来。