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

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

阅读量：3897 次

发布时间：2019-05-23

本文共 1015 字，大约阅读时间需要 3 分钟。

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

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

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

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

#include 
   
    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
    
     '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

转载地址：http://aruen.baihongyu.com/

你可能感兴趣的文章