//给定数列上的若干询问区间，求在不同的块长下，走完所有询问所需要的步数 //如果没有分块，那么步数就是询问长度之和，每跳一块就能节省$B-1$步，所以对于每个块长枚举每个块，求完整跨过该块的询问次数即可，不考虑被块包含的询问，则次数等于位于块左端点左侧的询问左端点数$-$位于块右端点左侧的询问右端点数，这样剩下的一定是左边开始一直到右边结束的，用树状数组维护即可；排除被包含的情况，只需要把询问的长度排序，倒序枚举块长，每次只加进来比块长长的询问即可 #include <iostream> #include <cstdio> #include <algorithm> #define LL long long using namespace std; const int MAX=1e6+5; struct ques{ int l,r,len; bool operator <(const ques &x)const{ return x.len<len; } }h[MAX]; int n,q,cc; int tree[2][MAX]; //0左1右 inline int lowbit(int x){return x&(-x);} inline void add(int x,int y,int type){for(;x<=n;x+=lowbit(x))tree[type][x]+=y;} inline int query(int x,int type){ int ret=0; for(;x;x-=lowbit(x))ret+=tree[type][x]; return ret; } LL ans[MAX]; int main(){ scanf("%d %d",&n,&q); for(int i=1;i<=q;i++)scanf("%d %d",&h[i].l,&h[i].r),h[i].len=h[i].r-h[i].l+1,ans[1]+=h[i].len; sort(h+1,h+q+1); for(int B=n;B>1;B--){ while(cc+1<=q && h[cc+1].len>B){ cc++; add(h[cc].l,1,0); add(h[cc].r,1,1); //cout<<h[cc].l<<" "<<h[cc].r<<endl; } ans[B]=ans[1]; for(int l=1,r=l+B-1;r<=n;l=r+1,r=l+B-1){ ans[B]-=1LL*(B-1)*(query(l,0)-query(r-1,1)); } if(B==2)break; } for(int i=1;i<=n;i++)printf("%lld ",ans[i]); return 0; }