E - Snuke Line
Time limit : 2sec / Memory limit : 256MB
Score : 700 points
Problem Statement
Snuke has decided to play a game, where the player runs a railway company. There are M+1 stations on Snuke Line, numbered 0 through M. A train on Snuke Line stops at station 0 and every d-th station thereafter, where d is a predetermined constant for each train. For example, if d=3, the train stops at station 0, 3, 6, 9, and so forth.
There are N kinds of souvenirs sold in areas around Snuke Line. The i-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations li, li+1, li+2, …, ri.
There are M values of d, the interval between two stops, for trains on Snuke Line: 1, 2, 3, …, M. For each of these M values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station 0. Here, assume that it is not allowed to change trains.
Constraints
1≦N≦3×105
1≦M≦105
1≦li≦ri≦M
Input
The input is given from Standard Input in the following format:
N M
l1 r1
:
lN rN
Output
Print the answer in M lines. The i-th line should contain the maximum number of the kinds of souvenirs that can be purchased if one takes a train stopping every i-th station.
Sample Input 1
3 3
1 2
2 3
3 3
Sample Output 1
3
2
2
If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.
If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.
If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.
Sample Input 2
7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4
Sample Output 2
7
6
6
5
4
5
5
3
2
题意：列车在长度为M的街道上行走，有M个站，现在列车将会每隔d站停一下，如d=3时，将在0，3，6，9…站停，d的值是 1 ~ M，现在有N种礼物，每种礼物可以在Li ~ Ri站买到，问d为不同值时，都可以买到多少种礼物。输出d从1~M不同停站方式所能买到的礼物种类。
实际上是对于每个站点被不同礼物覆盖了多少次的单点查询，以及对每个礼物的区间更新，分别在哪些站可以买到。更新可能只有nlog,但查询，对于每个站点都查询一次，对于一个d就有n/d次logn的查询，然而这个d 还有m个，相当于d=1时就有nlogn次查询，更不用说d=2,3…时所有更新的求和。
可以想到，一个礼物，若其覆盖的区间长度，大于d，说明肯定跨越了大于1个站的范围。因此对于这些礼物，只需判断其长度即可得知是否能买到，因此，对于d，所有区间范围大于d的礼物都是可以买到的，这些不用查询，直接加上。
因此一开始输入时，可以将礼物按区间长度分类。当计算d能买到的礼物数量时，所有小于d的礼物被更新到线段树或树状数组上，用于查询每个站点被覆盖次数。从间隔小的d开始查询，需要做区间更新的礼物将一开始很少，因为大于d的区间非常多，而此时直接加上这些礼物个数即可。然后更新小于d的区间将被记录到树上，并且从头至尾只会记录一次，后期可以直接用这些小区间的覆盖，而那些大于d的数量，初始是n，在每次遍历d时，会直接减掉小于d的区间。
因此并不会因为又从树上查询加，又通过直接加大于d的个数而重复加礼物，因为两种情况并没有重叠。
线段树区间更新单点查询
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
const int maxn=1e5+10;
struct num
{
int l,r;
} a[3*maxn];
struct node
{
int l,r,sum,mark;
} tre[maxn<<2];
void build(int l,int r,int rt)
{
tre[rt].l=l;
tre[rt].r=r;
tre[rt].mark=0;
if(l==r)
{
tre[rt].sum=0;
return ;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
tre[rt].sum=tre[rt<<1].sum+tre[rt<<1|1].sum;
return ;
}
void pushdown(int rt)
{
if(tre[rt].mark)
{
tre[rt<<1].sum+=(tre[rt<<1].r-tre[rt<<1].l+1)*tre[rt].mark;
tre[rt<<1|1].sum+=(tre[rt<<1|1].r-tre[rt<<1|1].l+1)*tre[rt].mark;
tre[rt<<1].mark+=tre[rt].mark;
tre[rt<<1|1].mark+=tre[rt].mark;
tre[rt].mark=0;
}
}
void update(int l,int r,int val,int rt)
{
if(tre[rt].l>=l&&tre[rt].r<=r)
{
tre[rt].sum+=(tre[rt].r-tre[rt].l+1)*val;
tre[rt].mark+=val;
}
else
{
pushdown(rt);
int mid=(tre[rt].l+tre[rt].r)>>1;
if(l>mid) update(l,r,val,rt<<1|1);
else if(r<=mid) update(l,r,val,rt<<1);
else
{
update(l,r,val,rt<<1);
update(l,r,val,rt<<1|1);
}
tre[rt].sum=tre[rt<<1].sum+tre[rt<<1|1].sum;
}
}
int query(int pos,int rt)
{
if(tre[rt].l==pos&&tre[rt].r==pos) return tre[rt].sum;
else
{
pushdown(rt);
int mid=(tre[rt].l+tre[rt].r)>>1;
if(pos>mid)return query(pos,rt<<1|1);
else if(pos<=mid) return query(pos,rt<<1);
}
}
int n,m;
vector<int>q[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<=m; i++)q[i].clear();
for(int i=1; i<=n; i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
q[a[i].r-a[i].l+1].push_back(i);
}
build(1,m,1);
for(int i=1; i<=m; i++)
{
int ans=0;
n-=q[i].size();
for(int j=0; j<q[i].size(); j++) update(a[q[i][j]].l,a[q[i][j]].r,1,1);
for(int j=i; j<=m; j+=i) ans+=query(j,1);
printf("%d
",ans+n);
}
}
树状数组区间更新单点查询
根据对区间起点和终点的标记，求前缀和即可得到每个点的被覆盖次数
【以下引用莫老师的树状数组写法 @银月清歌】
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
#define M(a,b) memset(a,b,sizeof(a))
#define pb push_back
const int maxn = 100000+10;
const LL mod = 1000000007;
struct Node
{
int l,r;
bool operator < (const Node &a)const
{
return (r-l+1)<(a.r-a.l+1);
}
} s[maxn+(maxn<<1)];
vector<int>g[maxn];
int c[maxn];
int n,m;
void add(int l,int r)
{
while(l<=m)
{
++c[l];
l+=l&(-l);
}
while(r<=m)
{
--c[r];
r+=r&(-r);
}
return ;
}
int query(int i)
{
int res=0;
while(i)
{
res+=c[i];
i-=i&(-i);
}
return res;
}
int main()
{
M(c,0);
scanf("%d%d",&n,&m);
for (int i=0; i<=m; ++i)
{
g[i].clear();
}
for (int i=1; i<=n; ++i)
{
scanf("%d%d",&s[i].l,&s[i].r);
int len=s[i].r-s[i].l+1;
g[len].pb(i);
}
for(int i=1; i<=m; ++i)
{
int ans=0;
for (int j=0; j<g[i].size(); ++j)
{
int &pos=g[i][j];
add(s[pos].l,s[pos].r+1);
}
for (int j=i; j<=m; j+=i)
{
ans+=query(j);
}
n-=g[i].size();
printf("%d
",ans+n);
}
return 0;
}