The Preliminary Contest for ICPC Asia Shanghai 2019 B Light bulbs （离散的差分）

复杂度分析，询问一千次，区间长1e6，O（1e9）超时。

那么我们知道对于差分来说，没必要一个一个求，只需要知道区间长就可以了，所以我们定义结构体差分节点，一个头结点，一个尾节点。

这样tail.loc-head.loc就是整个区间长，该区间的实际的大小就是 Add标记的大小，Add标记就是从头加到尾。

排序2*m个差分节点，对于loc相同的节点，说明是同一个位置的差分，add合并就可以了，不需要进行统计，直接跳过本次循环。

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e3+10;

const int INF=0x3f3f3f3f;

int T,N,M,L,R;

struct Node {

    int loc,add;

}node[maxn];

bool cmp(const Node &a,const Node &b)

{

    return a.loc<b.loc;

}

long long getAns()

{

    M*=2;

    sort(node,node+M,cmp);

    long long ans=0,tmp=0;

    for (int i=0;i<M-1;i++) {

        if (node[i].loc==node[i+1].loc) {

            tmp+=node[i].add;

            continue;

        }

        tmp+=node[i].add;

        ans+=(tmp%2)*(node[i+1].loc-node[i].loc);

    }

    return ans;

}

inline int read()

{

    int f=1,num=0;

    char ch=getchar();

    while (ch>'9'||ch<'0') {

        if (ch=='-') {

            f=-1;

        }

        ch=getchar();

    }

    while (ch>='0'&&ch<='9') {

        num=num*10+ch-'0';

        ch=getchar();

    }

    return num*f;

}

inline void print(int x)

{

    if (x<0) {

        putchar('-');

    }

    if (x>9) {

        print(x/10);

    }

    putchar(x%10+'0');

}

int main()

{

    int kase=1;

    //scanf("%d",&T);

    T=read();

    while (T--) {

        N=read(),M=read();

        //scanf("%d%d",&N,&M);

        for (int i=0;i<2*M;i++) {

            node[i].add=node[i].loc=0;

        }

        for (int i=0;i<M;i++) {

            L=read(),R=read();

            //scanf("%d%d",&L,&R);

            node[i].loc=L;

            node[i+M].loc=R+1;

            node[i].add++;

            node[i+M].add--;

        }

        printf("Case #%d: %lld\n",kase++,getAns());

    }

    return 0;

}

巴特西

The Preliminary Contest for ICPC Asia Shanghai 2019 B Light bulbs （离散的差分）

最新文章

热门文章