10.22

T1 战争

【题目描述】

给你一个长度为\(n\)、初始全为\(1\)的序列，进行\(m\)次操作。（\(n、m \le 5 \times 10^5\)）

• \(0 \,\ x\) : 将\(x\)位置赋值为\(0\)

• \(1 \,\ x\) : 将\(x\)位置赋值为\(1\)

• \(2 \,\ x\) : 查询包含\(x\)这一位置的全为\(1\)的连续子序列（若\(x\)位置为\(0\)，则输出\(0\)）

----------------------------------------------------------------------手动分割----------------------------------------------------------------------

傻逼题，直接上线段树 \(+\) 二分（不过有人用 \(odt\) 过了，还挺快）

\(Code：\)

#include<cstdio>
#include<algorithm>
using namespace std;
#define rg register
#define ll long long
struct ios{
    template<typename TP>
    inline ios operator >> (TP &x)
    {
        TP f=1;x=0;rg char c=getchar();
        for(;c>'9' || c<'0';c=getchar()) if(c=='-') f=-1;
        for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
        x*=f;
        return *this;
    }
    template<typename TP>
    inline ios operator << (TP x)
    {
        int top=0,s[66];
        if(x<0) x=-x,putchar('-');
        if(!x) putchar('0');
        while(x) s[++top]=x%10+'0',x/=10;
        while(top) putchar(s[top]),--top;
        return *this;
    }
    inline ios operator << (char s)
    {
        putchar(s);
        return *this;
    }
}io;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N=5e5+5;
int n,m,sum[N<<2];
bool vis[N];
inline void pushup(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
inline void build(int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(lson),build(rson);
    pushup(rt);
}
inline void update(int p,int val,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(p,val,lson);
    else update(p,val,rson);
    pushup(rt);
}
inline int query(int L,int R,int l,int r,int rt)
{
    if(L<=l && r<=R) return sum[rt];
    int mid=(l+r)>>1,ans=0;
    if(L<=mid) ans+=query(L,R,lson);
    if(R>mid) ans+=query(L,R,rson);
    return ans;
}
int main()
{
    freopen("war.in","r",stdin);
    freopen("war.out","w",stdout);
    io>>n>>m;
    build(1,n,1);
    for(rg int i=1,a,b;i<=m;++i)
    {
        io>>a>>b;
        if(!a)
        {
            if(vis[b]) continue;
            update(b,0,1,n,1),vis[b]=1;
        }
        else if(a==1)
        {
            if(!vis[b]) continue;
            update(b,1,1,n,1),vis[b]=0;
        }
        else
        {
            if(vis[b]) {puts("0");continue;}
            int l=1,r=b,mid=0,ans=0,ret=0;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(query(mid,b,1,n,1)==b-mid+1) ans=b-mid+1,r=mid-1;
                else l=mid+1;
            }
            l=b+1,r=n;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(query(b+1,mid,1,n,1)==mid-b) ret=mid-b,l=mid+1;
                else r=mid-1;
            }
            io<<ans+ret<<'\n';
        }
    }
    return 0;
}

T2 魔法

【题目描述】

给你\(n\)对数\(a_i、b_i\)（\(n \le 5 \times 10^5\)），设\(c_k = a_i + b_j\)（\(i、j \le n\) ，\(k \le n^2\)），求前\(n\)小的\(c\)。

CSP考前模拟赛

原文：https://www.cnblogs.com/p-z-y/p/11718770.html