Bread （HG 2018.10.1 T1）

 你以为这是T1么。。 呵，太天真了，这是T3 没错今天的难度是倒着的 当然，第二题的思维难度大一些，第三题水题，这题。。暴力线段树。。。 加个快写就可以过了 那么就不多讲了 ``` #include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,p,q; int f[1000100]; void write(int x) { if(x<0) putchar('-'),x=-x; if(x>=10) write(x/10); putchar(x%10+'0'); } struct Col { int l,r; }c[10000100]; struct node { int l,r,num,f; }tr[10000100]; void build(int x,int l,int r) { tr[x].l=l;tr[x].r=r; if(l==r){tr[x].num=0;return;} int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); } void pushdown(int x) { tr[x].f=0;tr[x*2].f=1;tr[x*2+1].f=1; tr[x*2].num=tr[x].num; tr[x*2+1].num=tr[x].num; tr[x].num=0; } void Change(int x,int l,int r,int num) { int L=tr[x].l,R=tr[x].r,mid=(L+R)/2; if(L>=l && R<=r) { tr[x].num=num; tr[x].f=1; return; } if(tr[x].f) pushdown(x); if(l<=mid) Change(x*2,l,r,num); if(r>mid) Change(x*2+1,l,r,num); } void Print(int x) { if(tr[x].num) { for(int i=tr[x].l;i<=tr[x].r;i++) f[i]=tr[x].num; return; } if(tr[x].l==tr[x].r) return; Print(x*2); Print(x*2+1); } int main() { freopen("bread.in","r",stdin); freopen("bread.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&q); for(int i=max(m-n,1);i<=m;i++) { c[i].l=(i*p+q)%n+1; c[i].r=(i*q+p)%n+1; if(c[i].l>c[i].r) swap(c[i].l,c[i].r); } build(1,1,n); for(int i=max(m-n,1);i<=m;i++) Change(1,c[i].l,c[i].r,i); Print(1); for(int i=1;i<=n;i++) write(f[i]),puts(""); return 0; } ```