首页 > 代码库 > 【差分数列】tyvj2042线段问题

【差分数列】tyvj2042线段问题

2024-07-09 10:54:30   223人阅读

线段问题

描述 Description

有N条线段，已知每条线段的起点和终点（50000以内），然后有M个询问，每次询问一个点（50000以内），求这个点在多少条线段上出现过？

输入格式 InputFormat

第一行N线段条数
接下来N行，每行两个数，线段的起点和终点
第N+2行一个数M询问个数
接下来M行，每行一个点

输出格式 OutputFormat

对于每个询问，求答案
 

样例输入 SampleInput 

样例输出 SampleOutput 

数据范围和注释 Hint

N,M<=50000

思路 thinkings

这道题很水就水在没有要求在线算法，全部读进去让我一起输答案，于是差分数列大行其道……

这题本来是拿来练习线段树的，我是不是太直接了……

代码 code

#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>using namespace std;int cf[50005];          //差分数列，表示第i-1个和第i个的差，即cf[i]=数列[i]-数列[i-1];int sum[50005];      //差分数列的前缀和就是原数列。。。int main(){    int i,j,m,n,p,first,last,size;    cin>>n;    memset(cf,0,sizeof(cf));    memset(sum,0,sizeof(sum));     size=0;    for (i=1;i<=n;i++)     {        cin>>first>>last;        cf[first]+=1; cf[last+1]-=1;        size=max(last,size);    }    for (i=0;i<=size;i++)    sum[i]=sum[i-1]+cf[i];    cin>>m;    for (i=1;i<=m;i++)    {        cin>>p;        cout<<sum[p]<<endl;    }    return 0;}

反思

（1）看题目要先看清楚是在线还是离线，没有要求强制在线离线还是好用啊。。。

（2）两句老话：差分数列的前缀和是原数列

                     前缀和的差分数列是原数列

 （3）这题特别坑的地方在于

    for (i=0;i<=size;i++)    sum[i]=sum[i-1]+cf[i];

        如果不幸写成：

    for (i=1;i<=size;i++)    sum[i]=sum[i-1]+cf[i];

        就全WA了。。。。。。

 

 


联系
我们