先断环成链，由于对于多组询问不好一起处理，我们先考虑单组询问的处理方式。
一个很暴力的想法是每次模拟题目要求的操作并且最后数颜色，我们这是在通过下标进行操作最后再数颜色，而很多对于下标的操作都是不必要的，考虑直接枚举颜色进行判定。
对于每种颜色，它对于最后答案有贡献当且仅当它可以存活到那个时刻，即每次延伸出去的点都没有被后来的操作所覆盖。
考虑刻画这个“没有被覆盖”的条件，由于该颜色区间的左右边界一定单调移动，一个想法是正着考虑，每次维护当前颜色所在区间的左右端点，每次操作对若干区间进行处理，但是这种做法比较不好维护且扩展性较差。
再转换一下思路，注意到一个颜色能存活其实等价于自己存活或者延伸出去的节点能存活，而延伸出去的节点和自己存活的时间都会在后面进行计算，我们考虑倒着进行操作。
记 \(t_i\) 表示第 \(i\) 个节点及其延伸最后一次被覆盖的时间（注意到这里是第 \(i\) 个节点及其延伸，我们不考虑的前面与它相同的节点），第 \(k\) 每次操作相当于：
\[i\in[l+1,r],t_i\leftarrow k
\]
\[t_l \leftarrow \max_{j\in [l+1,r]} t_j
\]
初始时 \(t_i=\infty\)，我们倒着进行所有的操作，第 \(x\) 个时刻开始的答案就等价于 \(t_i>x+k-1\) 的位置个数，而这个做法推广到多组询问也是容易的。
最后一个问题是我们如何快速维护上述操作，由于这里有推平操作，我们考虑维护 \(t\) 相等的连续段并尝试证明复杂度，注意到一开始 \(t\) 相同的连续段有 \(n\) 个，每次遍历连续段的同时也是在推平，每次新建的连续段也是 \(O(1)\) 的，也就是说遍历的连续段总数就是 \(O(n)\) 的。
因此，我们只要用 set 维护连续段，树状数组维护数点，即可完成此题，时间复杂度 \(O(n \log n)\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>
#define itt set<inter>::iterator
#define N 500005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='-' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x){
if(x/10)write(x/10);
putchar(x%10+'0');
}
struct BIT{
int a[N];
int lowbit(int x){return x&(-x);}
void add(int x,int val){while(x<N){a[x]+=val;x+=lowbit(x);}}
int ask(int x){int ans=0;while(x){ans+=a[x];x-=lowbit(x);}return ans;}
}T;
int l[N],r[N],an[N];
struct inter{
int l,r,val;
inter(int l,int r,int val):l(l),r(r),val(val){}
};
bool operator <(inter x,inter y){
return (x.l==y.l?x.l<y.l:x.r<y.r);
}
set<inter> t;
void split(int x){
itt it=t.lower_bound(inter(x,x,0));
if(it==t.end() || (it->l)>x)it--;
if(it->r==x)return;
int tl=it->l,tr=it->r,tval=it->val;
t.erase(it);t.insert(inter(tl,x,tval));t.insert(inter(x+1,tr,tval));
}
int main(){
int n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)l[i]=read(),r[i]=read();
for(int i=m+1;i<=m+k-1;i++)l[i]=l[i-m],r[i]=r[i-m];
for(int i=1;i<=n;i++)t.insert(inter(i,i,N-1)),T.add(N-1,1);
for(int i=m+k-1;i>=1;i--){
split(l[i]-1);split(r[i]);
itt it=t.lower_bound(inter(l[i],l[i],0)),itl=it;
int ans=it->val;
for(;it!=t.end() && (it->r)<=r[i];it++){
int siz=(it->r)-(it->l)+1;T.add(it->val,-siz);
ans=max(ans,it->val);
}
t.erase(itl,it);
t.insert(inter(l[i],l[i],ans));T.add(ans,1);
if(r[i]>l[i])t.insert(inter(l[i]+1,r[i],i)),T.add(i,r[i]-l[i]);
if(i<=m)an[i]=T.ask(N-1)-T.ask(i+k-1);
}
for(int i=1;i<=m;i++)write(an[i]),putchar(' ');
}