【NOIP2015 模拟11.2晚】JZOJ8月4日提高组T2 我的天

题目

很久很以前，有一个古老的村庄——xiba村，村子里生活着n+1个村民，但由于历届村长恐怖而且黑暗的魔法统治下，村民们各自过着独立的生活，完全没有意识到其他n个人的存在。
但有一天，村民xiba臻无意中也得到了魔法，并发现了这个恐怖的事实。为了反抗村长，他走遍了全世界，找到了其他n个村民，并组织他们发动革命。但让这n个素不相识的村民（xiba臻已跟他们认识）同心协力去抵抗村长是很困难的，所以xiba臻决定先让他们互相认识。
这里，xiba臻用了xiba村特有的xiba思维：先让这n个人排成一列，并依次从1-n标号。然后每次xiba臻会选出一个区间[l, r]，在这个区间中的人会去认识其他在这个区间中的人，但已经认识过得不会再去认识。这样，进行m次操作后，xiba臻认为这n个人能认识到许多人。
但是，为了精确地知道当前有多少对人已经认识了，xiba臻想要知道每次操作后会新产生出多少对认识的人，但这已是xiba思维无法解决的事了，你能帮帮他吗？

对于20%的数据，1≤n，m≤100。
对于50%的数据，1≤n，m≤5000。
对于100%的数据，1≤n，m≤300000，1≤li≤ri≤n。

题解

题意很显明

就是给出一个序列，每次操作一个区间，这个区间的每个人会和其他没有认识过的人认识，问每次操作后新增了多少对认识的人

其实在一开始

这题是可以暴力水过的

然而因为lihui这个大帅哥（kēngbī）改了数据使得暴力成功被卡

来让我们思考正解

设f[i]表示第i个人与i+1~f[i]的人认识，初始f[i]=i

然后一次操作后f[i]=max{f[i],r} （l<=i<=r） ,同时统计答案

时间复杂度很明显是O(nm)的，只能过50%的数据

发现f[i]是具有单调性的，所以当f[i]>=r时直接退出

但这样原本是可以过的，由于数据改了，所以要更加优化

因为f是单调的，那么记录区间最大，最小和区间和

然后用线段树维护一下就好了

#include<cstdio>

#include<iostream>

using namespace std;

struct node

{

    long long mx,mn,sum;

}tree[1200005];

long long n,m,i,x,y,lazy[1200005];

void build(long long now,long long l,long long r)

{

    long long mid;

    if (l==r)

    {

        tree[now].sum=tree[now].mx=tree[now].mn=l;

        return;

    }

    mid=(l+r)>>1;

    build(now<<1,l,mid);

    build(now<<1|1,mid+1,r);

    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;

    tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);

    tree[now].mn=min(tree[now<<1].mn,tree[now<<1|1].mn);

}

void update(long long x,long long u,long long v,long long w)

{

    if (lazy[x]!=0)

    {

        lazy[x<<1]=lazy[x];

        lazy[x<<1|1]=lazy[x];

        tree[x<<1].sum=(v-u+1)*lazy[x];

        tree[x<<1|1].sum=(w-v)*lazy[x];

        tree[x<<1].mx=tree[x<<1].mn=tree[x<<1|1].mx=tree[x<<1|1].mn=lazy[x];

        lazy[x]=0;

    }

}

long long query(long long now,long long l,long long r,long long x,long long y,long long c)

{

    long long res,mid;

    if (c<=tree[now].mn) return 0;

    if (l==r)

    {

        if (c<=tree[now].mx) return 0;

        res=c-tree[now].sum;

        tree[now].sum=tree[now].mx=tree[now].mn=c;

        return res;

    }

    mid=(l+r)>>1;

    if (c<tree[now].mx)

    {

        update(now,l,mid,r);

        if (y<=mid)

        {

            res=query(now<<1,l,mid,x,y,c);

        }

        else if (x>mid)

        {

            res=query(now<<1|1,mid+1,r,x,y,c);

        }

        else res=query(now<<1,l,mid,x,mid,c)+query(now<<1|1,mid+1,r,mid+1,y,c);

        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;

        tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);

        tree[now].mn=min(tree[now<<1].mn,tree[now<<1|1].mn);

        return res;

    }

    else

    {

        if (l==x&&r==y)

        {

            lazy[now]=c;

            tree[now].mx=c;

            tree[now].mn=c;

            res=tree[now].sum;

            tree[now].sum=c*(r-l+1);

            return tree[now].sum-res;

        }

        else

        {

            update(now,l,mid,r);

            if (y<=mid)

            {

                res=query(now<<1,l,mid,x,y,c);

            }

            else if (x>mid)

            {

                res=query(now<<1|1,mid+1,r,x,y,c);

            }

            else res=query(now<<1,l,mid,x,mid,c)+query(now<<1|1,mid+1,r,mid+1,y,c);

            tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;

            tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);

            tree[now].mn=min(tree[now<<1].mn,tree[now<<1|1].mn);

            return res;

        }

    }

}

int main()

{

    freopen("ohmygod.in","r",stdin);

    freopen("ohmygod.out","w",stdout);

    scanf("%lld%lld",&n,&m);

    build(1,1,n);

    for (i=1;i<=m;i++)

    {

        scanf("%lld%lld",&x,&y);

        printf("%lld\n",query(1,1,n,x,y,y));

    }

    fclose(stdin);

    fclose(stdout);

    return 0;

}

【NOIP2015模拟11.2晚】JZOJ8月4日提高组T2 我的天

【NOIP2015 模拟11.2晚】JZOJ8月4日提高组T2 我的天

题目

题解