Atcoder 068E

题目链接：http://arc068.contest.atcoder.jp/tasks/arc068_c

题目大意：有m个车站排成一列，有n种纪念品，第i种只能在l[i]和r[i]之间的车站买到，列车从0出发，每d站停一次，求对于1<=d<=m，分别最多能买到多少种纪念品？

分析：对于长度大于等于d的区间，肯定可以到达，可以从小枚举d，把长度小于d的区间加1，求k*d的和，再加上长度大于等于d的区间个数就是答案，复杂度为O(mlogm+nlogn)。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 const int maxn=3e5+5,maxm=1e5+5;
 7 int m,n;
 8 struct Pair{
 9     int l,r;
10 }p[maxn];
11 bool Cmp(Pair a,Pair b){return a.r-a.l<b.r-b.l;}
12 class segTree{
13     int a[maxn],s[maxn*4],tag[maxn*4];
14 public:
15     segTree(){memset(a,0,sizeof(a));}
16     void build(int node,int begin,int end){
17         tag[node]=0;
18         if(begin==end){
19             s[node]=a[begin];
20         }else{
21             build(2*node,begin,(begin+end)/2);
22             build(2*node+1,(begin+end)/2+1,end);
23             s[node]=s[2*node]+s[2*node+1];
24         }
25     }
26     void pushdown(int node,int begin,int end){
27         if(begin==end){
28             s[node]+=tag[node];
29             a[begin]=s[node];
30         }else{
31             tag[2*node]+=tag[node];
32             tag[2*node+1]+=tag[node];
33             s[node]+=tag[node]*(end-begin+1);
34         }
35         tag[node]=0;
36     }
37     void Change(int node,int begin,int end,int left,int right,int add){
38         if(begin>=left&&end<=right){
39             tag[node]+=add;
40         }else{
41             pushdown(node,begin,end);
42             int m=(begin+end)/2;
43             if(!(right<begin||left>m)){
44                 Change(2*node,begin,m,left,right,add);
45             }
46             if(!(right<m+1||left>end)){
47                 Change(2*node+1,m+1,end,left,right,add);
48             }
49         }
50     }
51     int query(int node,int begin,int end,int idx){
52         pushdown(node,begin,end);
53         if(begin==end)return a[begin];
54         int m=(begin+end)/2;
55         if(idx<=m)return query(2*node,begin,m,idx);
56         return query(2*node+1,m+1,end,idx);
57     }
58 }st;
59 int main(){
60     scanf("%d%d",&n,&m);
61     st.build(1,1,m);
62     for(int i=0;i<n;i++)
63         scanf("%d%d",&p[i].l,&p[i].r);
64     sort(p,p+n,Cmp);
65     int i=0;
66     for(int d=1;d<=m;d++){
67         while(i<n&&p[i].r-p[i].l<d){
68             st.Change(1,1,m,p[i].l,p[i].r,1);
69             i++;
70         }
71         int ans=n-i;
72         for(int k=d;k<=m;k+=d){
73             ans+=st.query(1,1,m,k);
74         }
75         printf("%d
",ans);
76     }
77     return 0;
78 }