路灯「APIO 2019」

标签：lowbit   fine   ||   题意   一个   c++   ++i   reg   ret   

题意

有、复杂，自己上网搜

思路

\((x,y)\) 表示从\(x\)到\(y\)联通的时间长度。

那么查询操作相当于二维平面上的单点查询。

对于每一个\(i\)，维护一个最左能到达的\(lm\)，和最右能到达的\(rm\)。

那么对于每一个更新操作，相当于对左上角为\((lm,i)\)，右下角为\((i,rm)\)的矩形做修改。

于是就转换为类似「简单题」的题目了，可以CDQ分治解决，当然也可以直接上树套树。

代码

#include 

using namespace std;

namespace StandardIO {
    
    template inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c inline void write (T x) {
        if (x=10) write(x/10);
        putchar(x%10+'0');
    }
    
}

using namespace StandardIO;

namespace Solve {
    #define int long long
    
    const int N=300003;
    
    int n,q,sta,cnt;
    char s[N];
    int tree[N];
    struct node {
        int t,x,y,id;
        int type,val,ans;
        node () {}
        node (int _t,int _x,int _y,int _ty,int _v,int _i) : t(_t),x(_x),y(_y),type(_ty),val(_v),id(_i) {}
    } w[N S;
    
    inline int pre (int x) {
        set::iterator it=S.lower_bound(x);
        return *(--it);
    }
    inline int suc (int x) {
        set::iterator it=S.upper_bound(x);
        return *it;
    }
    inline int lowbit (int x) {
        return x&(-x);
    }
    inline void update (int x,int v) {
        for (register int i=x; i>1;
        int ptr_l=l,ptr_r=mid+1,num=l-1;
        while (ptr_l>1;
        CDQ(l,mid),CDQ(mid+1,r);
        int ptr=l-1;
        for (register int i=mid+1; i>op;
            if (op[0]=='t') {
                read(x),s[x]^=1;
                int l=pre(x)+1,r=suc(x)-1;
//              couty-1&&s[x]=='1'&&s[y-1]=='1') ans[sta]+=i;
            }
        }
        sort(w+1,w+cnt+1,cmpt);
//      for (register int i=1; i

路灯「APIO 2019」

标签：lowbit   fine   ||   题意   一个   c++   ++i   reg   ret   

原文地址：https://www.cnblogs.com/ilverene/p/11395880.html