loj #3146. 「APIO 2019」路灯

2021-05-29 06:03

阅读：419

标签：pair efi include mod 细节 https 如何分治 amp

loj #3146. 「APIO 2019」路灯

暴力的话就是查询\((l,r)\)之间是否全部是1，考虑如何优化查询

我们可以利用\(set\)来维护每一个全\(1\)区间和它出现的时间，具体的，用\((lp,rp,l,r)\)来表示\((lp,rp)\)的全\(1\)区间在时间\([l,r]\)中是存在的

那么对于一个在时间\(i\)的询问\((l_i,r_i)\)，\((lp,rp,l,r)\)会对它产生贡献当且仅当\(lp\leq l_i,rp\geq r_i,i\geq l\)，产生的贡献为\(min(i,r)-l+1\)

注意到限制的条件其实是类似于三维偏序的，将全\(1\)区间的四元组也当做询问，我们按照\(r\)值降序所有的询问，进行\(cdq\)分治

考虑前一半对后一半的贡献，两边分别按\(l\)升序排序，线段树维护这个类似区间长度的贡献即可

细节稍微有点小多,而且由于过度使用stl所以常数巨大

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef long double db;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct segnode{
    int lp,rp,l,r;
}seg[1200100];
struct qnode{
    int l,r,tim,id;
}q[300300];
struct tnode{
    int op,id,r;
}th[2002000];
int ans[300300];
int n,m,nowr[300300],id[300300],tot=0,sta[300300];
int tr[2002000],add[2002000],qtot=0,tot1=0;
set nowl;
set::iterator iter;
char s[300300],op[10];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch>1;
        tr[id=ql) && (r>1;
    if (qlmid) modify(id=ql) && (r>1,ans=0;pushdown(id,l,r);
    if (qlmid) ans+=query(idq.r;
    else return p.op>1;
    solve(l,mid);solve(mid+1,r);
    sort(th+l,th+mid+1,cmp2);
    sort(th+mid+1,th+r+1,cmp2);
    int p=l;
    rep(i,mid+1,r)
    {
        if (th[i].op==1) continue;
        while ((p=seg[th[p].id].lp))
        {
            modify(1,1,m,seg[th[p].id].l,seg[th[p].id].r,1);
            p++;
        }
        ans[th[i].id]+=query(1,1,m,1,q[th[i].id].tim);
    }
    rep(i,l,p-1) modify(1,1,m,seg[th[i].id].l,seg[th[i].id].r,-1);
}

int main()
{
    n=read();m=read();
    scanf("%s",s+1);
    rep(i,1,n) sta[i]=s[i]-'0';
    for (int i=1;ipos)
                {
                    id[pos+1]=(++tot);
                    seg[id[pos+1]]=(segnode){pos+1,r,i+1,m};
                    nowr[pos+1]=r;nowl.insert(pos+1);
                }
            }
        }
        else
        {
            q[++qtot].id=qtot;q[qtot].tim=i;
            q[qtot].l=read();q[qtot].r=read()-1;
         }
    }
    //rep(i,1,qtot) cout

loj #3146. 「APIO 2019」路灯

标签：pair efi include mod 细节 https 如何分治 amp

原文地址：https://www.cnblogs.com/encodetalker/p/11105339.html

上一篇：Win10 子系统Linnux部署tensorflow

下一篇：JDK1.8+API+中文文档+高清完整版（不要积分免费拿）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：loj #3146. 「APIO 2019」路灯
文章链接：http://soscw.com/index.php/essay/88990.html

亲，登录后才可以留言！

loj #3146. 「APIO 2019」路灯

loj #3146. 「APIO 2019」路灯

评论

热门文章

推荐文章

最新文章

置顶文章