【题解】暗星人
题面
给定 \(m\) 个操作 \(L_{i},R_{i},a_{i},b_{i},l_{i},r_{i},X_{i},x_{i},\)，对于 \(j\in[l_{i},r_{i}],X_{i}\in[L_{j},R_{j}]\)，令 \(x_{i}\leftarrow (a_{j}x_{i}+b_{j})\mod2677114440,y\leftarrow\max(y,b_{j})\)（按 \(j\) 递增的顺序），求 \(x_{i},y\)
强制在线
\(n\le 10^{6},m\le3\times10^{5},1\le L_{i}\le R_{i}\le n,1\le X_{i}\le n,1\le a_{i},b_{i},x_{i}\le10^{6},1\le l_{i}\le r_{i}\le i\)
\(2\)G, \(5\)s
分析
- \(m\) 这一维上单点修改 \(i\)，区间查询 \([l_{i},r_{i}]\)
- \(n\) 这一维上区间修改 \([L_{i},R_{i}]\)，单点查询 \(X_i\)
- 对 \(x\) 的操作可以看作矩阵乘法，满足结合律但不满足交换律，由于无法求逆元因此不具有可减性
- 对 \(y\) 的操作是取 \(\max\)，弱于对 \(x\) 的操作，因此下文只考虑 \(x\)
线段树套线段树
考场的第一想法
因为修改不具有交换律，所以区间修改无法标记永久化，需要下传标记，只能将 \(n\) 维放在内层，外层先左后右地查询即可保证顺序
考场 code
int i,n,m,type,L,R,a,b,ql,qr,X;
LL lstans,ans1,ans2;
int rd() { LL x; read(x); return type ? x^lstans : x; }
#define mid ((l+r)>>1)
#define ls(u) t[u].ch[0]
#define rs(u) t[u].ch[1]
struct Seg {
int ind;
struct Node { int ch[2],mxb; LL a,b; } t[int(6e7)];
int node() { t[++ind].a = 1; return ind; }
void down(int u,LL a,LL b)
{ (t[u].a *= a) %=mod, t[u].b = (a * t[u].b + b) %mod; }
void down(int u) {
if( t[u].a == 1 && !t[u].b ) return;
if( !ls(u) ) ls(u) = node(); if( !rs(u) ) rs(u) = node();
down(ls(u),t[u].a,t[u].b), down(rs(u),t[u].a,t[u].b);
t[u].a = 1, t[u].b = 0;
}
void add(int &u,int l=1,int r=n) {
if( !u ) u = node();
if( L <= l && r <= R ) return down(u,a,b), ckmax(t[u].mxb,b);
down(u);
if( L <= mid ) add(ls(u),l,mid);
if( mid < R ) add(rs(u),mid+1,r);
}
void query(int u,int l=1,int r=n) {
if( !u ) return;
ckmax(ans2,t[u].mxb);
if( (!ls(u) && !rs(u)) || l == r ) // here
return ans1 = (t[u].a * ans1 + t[u].b) %mod, void();
down(u);
X<=mid ? query(ls(u),l,mid) : query(rs(u),mid+1,r);
}
} seg;
#undef ls
#undef rs
#define ls (u<<1)
#define rs (u<<1|1)
int rt[int(1.2e6)];
void add(int u=1,int l=1,int r=m) {
seg.add(rt[u]);
if( l == r ) return;
i<=mid ? add(ls,l,mid) : add(rs,mid+1,r);
}
void query(int u=1,int l=1,int r=m) {
if( ql <= l && r <= qr ) return seg.query(rt[u]);
if( ql <= mid ) query(ls,l,mid);
if( mid < qr ) query(rs,mid+1,r);
}
#undef mid
#undef ls
#undef rs
signed main() { freopen("ex_dark1.in","r",stdin); freopen("dark.out","w",stdout);
read(n,m,type);
for(i = 1; i <= m; ++i) {
L = rd(), R = rd(), a = rd(), b = rd(), ql = rd(), qr = rd(), X = rd(),
ans1 = rd(), ans2 = 0;
add(), query();
write(lstans=ans1^ans2);
}
cerr<时空复杂度 \(O(n\log m\log n)\)，MLE
考场看到 2G 内存直接莽上去了，30min 码完没怎么调就过了小样例，心理活动类似 wcr 在某次模拟赛后说：“今天我光宗耀祖了”
分块套线段树
MLE 的原因是需要在外层树的 \(\log\) 个结点上作区间修改（每次修改在内层树上建 \(\log\) 个点）
为了减少修改次数，可以把外层线段树换成分块，只需要在 \(1\) 个块对应的线段树上修改
考场 code
const int N = 1e6+5, B = 2e3, BN = N/B+5;
int i,n,m,type,L[N],R[N],a[N],b[N],ql,qr,X,in[N],rt[BN];
LL lstans,ans1,ans2;
int rd() { LL x; read(x); return type ? x^lstans : x; }
#define mid ((l+r)>>1)
#define ls(u) t[u].ch[0]
#define rs(u) t[u].ch[1]
struct Seg {
int ind;
struct Node { int ch[2],mxb; LL a,b; } t[int(2e7)];
int node() { t[++ind].a = 1; return ind; }
void down(int u,LL a,LL b)
{ (t[u].a *= a) %=mod, t[u].b = (a * t[u].b + b) %mod; }
void down(int u) {
if( !ls(u) ) ls(u) = node(); if( !rs(u) ) rs(u) = node();
down(ls(u),t[u].a,t[u].b), down(rs(u),t[u].a,t[u].b);
t[u].a = 1, t[u].b = 0;
}
void add(int &u,int l=1,int r=n) {
if( !u ) u = node();
if( L[i] <= l && r <= R[i] )
return down(u,a[i],b[i]), ckmax(t[u].mxb,b[i]);
if( t[u].a > 1 || t[u].b ) down(u);
if( L[i] <= mid ) add(ls(u),l,mid);
if( mid < R[i] ) add(rs(u),mid+1,r);
}
void query(int u,int l=1,int r=n) {
if( !u ) return;
ckmax(ans2,t[u].mxb);
if( (!ls(u) && !rs(u)) || l == r )
return ans1 = (t[u].a * ans1 + t[u].b) %mod, void();
if( t[u].a > 1 || t[u].b ) down(u);
X<=mid ? query(ls(u),l,mid) : query(rs(u),mid+1,r);
}
} seg;
#undef ls
#undef rs
#define solve(j) if( L[j] <= X && X <= R[j] ) ans1 = (a[j] * ans1 + b[j]) %mod, ckmax(ans2,b[j])
void bf(int l,int r) {
int j = l;
for(; j+3 <= r; j += 4) {
solve(j);solve(j+1);solve(j+2);solve(j+3);
// solve(j+4);solve(j+5);solve(j+6);solve(j+7);
}
for(; j <= r; ++j) solve(j);
}
signed main() { freopen("dark.in","r",stdin); freopen("dark.out","w",stdout);
read(n,m,type);
For(i,1,m) in[i] = (i-1)/B+1;
for(i = 1; i <= m; ++i) {
L[i] = rd(), R[i] = rd(), a[i] = rd(), b[i] = rd(),
ql = rd(), qr = rd(), X = rd(), ans1 = rd(), ans2 = 0;
seg.add(rt[in[i]]);
int l = in[ql], r = in[qr];
if( l+1 >= r ) bf(ql,qr);
else {
bf(ql,l*B);
Rep(i,l+1,r) seg.query(rt[i]);
bf(r*B-B+1,qr);
}
write(lstans=ans1^ans2);
}
cerr<时间复杂度 \(O(m\sqrt{m\log n})\)，空间复杂度 \(O(m\log n)\)
线段树套平衡树
另一种想法是降低修改的代价，即把内层树换成动态开点平衡树，这样每次修改只需要新建 \(O(1)\) 个结点
code
int i,n,m,type,L,R,a,b,ql,qr,X;
U lstans,ans1,ans2;
int rd() { LL x; read(x); return type ? x^lstans : x; }
unsigned mt() {
static unsigned z1=67451325,z2=53487576,b=35735863;
b=((z1<<6)^z1)>>13,z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27,z2=((z2&4294967288U)<<2)^b;
return z1^z2;
}
#define ls(u) t[u].ch[0]
#define rs(u) t[u].ch[1]
#define len(u) (t[u].r-t[u].l+1)
struct BST {
int ind;
struct Node { int ch[2],l,r,siz,mxb,mxbb; U a,b,aa,bb; } t[int(2e7)];
int node(int l,int r) { return t[++ind] = {0,0,l,r,r-l+1,0,0,1,0,1,0}, ind; }
void up(int u) { t[u].siz = t[ls(u)].siz+t[rs(u)].siz+len(u); }
void down(int u,LL a,LL b,int mxb) {
t[u].a = t[u].a*a %mod, t[u].b = (a*t[u].b+b) %mod, ckmax(t[u].mxb,mxb),
t[u].aa = t[u].aa*a%mod, t[u].bb = (a*t[u].bb+b)%mod, ckmax(t[u].mxbb,mxb);
}
void down(int u) {
if( t[u].aa == 1 && !t[u].bb ) return;
if( ls(u) ) down(ls(u),t[u].aa,t[u].bb,t[u].mxbb);
if( rs(u) ) down(rs(u),t[u].aa,t[u].bb,t[u].mxbb);
t[u].aa = 1, t[u].bb = t[u].mxbb = 0;
}
void split(int u,int k,int &l,int &r) {
if( !u ) return l = r = 0, void();
down(u);
if( t[u].l <= k && k < t[u].r ) {
int v = ++ind; t[v] = t[u];
t[u].r = k, t[v].l = k+1;
ls(v) = 0, rs(u) = v, up(v), up(u);
}
if( k < t[u].l ) r = u, split(ls(u),k,l,ls(r)), up(r);
else l = u, split(rs(u),k,rs(l),r), up(l);
}
bool rnd(int x,int y) { return mt()%(x+y) < x; }
int merge(int l,int r) {
if( !l || !r ) return l | r;
int u;
if( rnd(t[l].siz,t[r].siz) ) down(u=l), rs(l) = merge(rs(l),r);
else down(u=r), ls(r) = merge(l,ls(r));
return up(u), u;
}
void add(int &u) {
int l,r,mid; split(u,R,l,r), split(l,L-1,l,mid);
down(mid,a,b,b), u = merge(l,merge(mid,r));
}
void query(int u,int k) {
if( t[u].l <= k && k <= t[u].r ) {
ans1 = ((LL)t[u].a*ans1+t[u].b) %mod, ckmax(ans2,t[u].mxb);
return;
}
down(u);
k>1)
int rt[int(1.2e6)];
vector> t[int(1.2e6)];
void add(int u=1,int l=1,int r=m) {
t[u].pb(L,R,a,b);
if( l == r ) return;
i<=mid ? add(ls,l,mid) : add(rs,mid+1,r);
}
void query(int u=1,int l=1,int r=m) {
if( ql <= l && r <= qr ) {
if( !rt[u] ) rt[u] = fhq.node(1,n);
for(auto &i : t[u]) tie(L,R,a,b) = i, fhq.add(rt[u]);
t[u].clear();
return fhq.query(rt[u],X);
}
if( ql <= mid ) query(ls,l,mid);
if( mid < qr ) query(rs,mid+1,r);
}
#undef ls
#undef rs
#undef mid
signed main() { freopen("dark.in","r",stdin); freopen("dark.out","w",stdout);
read(n,m,type);
for(i = 1; i <= m; ++i) {
L = rd(), R = rd(), a = rd(), b = rd(), ql = rd(), qr = rd(), X = rd();
ans1 = rd(), ans2 = 0, add(), query();
write(lstans=ans1^ans2);
}
return ocl();
}
时间复杂度 \(O(m\log m\log n)\)，空间复杂度 \(O(m\log m)\)，常数过大 TLE
分块
想法与树套树完全不同
注意到本题和一般的插入、查询操作不同，每次加点的块一定是散块，这意味着其实不需要支持插入，每个块在元素满了之后才需要构建一次
一个块中的操作可以将 \(n\) 这一维分成 \(2B\) 段，而块内操作对每段的影响是相同的，因此可以离散化后 \(O(B)\) 暴力处理每段的答案
code by szs
#include
using namespace std;
#define uu unsigned
#define scanf abc=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define forg(i,x) for(int i=fir[x];i;i=nxt[i])
#define int unsigned
int abc;
typedef long long ll;
typedef uu long long ull;
typedef pairpii;
typedef vectorVI;
mt19937 rnd((ull)(new char));
int rd(int l,int r){uniform_int_distribution<>ee(l,r);return ee(rnd);}
void NC(ull k){cout<<(k>>20)<=lx[i]&&X<=rx[i])m0=m0*d[i],R1=max(R1,V[i]);
}
void SLV(int k){
// if(!po[k][X])return;
int l=el[k]+1,r=er[k],md;if(X=xl[r])return;
while(l!=r){md=(l+r+1)>>1;if(X>=xl[md])l=md;else r=md-1;}
// int l=po[k][X];
m0=m0*jz[l],R1=max(R1,qz[l]);
}
void slv(int k,int L,int R,int A,int B,int l,int r,int v0){
lx[k]=L,rx[k]=R,V[k]=B;d[k]=mat(A,0,B,1);R1=0,m0=mat(v0,1);
if(be[l]==be[r])return BF(l,r);
BF(l,rp[be[l]]);
for(int i=be[l]+1;i=lx[i]&&p<=rx[i])mx=max(mx,V[i]),m0=m0*d[i];
xl[++N]=p,jz[N]=m0,qz[N]=mx;
// if(T!=nn){for(int i=li[T];i>n>>n>>TP;fki();
int la=0;
for(int T=1;T<=n;++T){
int L=red(),R=red(),a=red(),b=red(),l=red(),r=red(),_X=red(),x=red();X=_X;
la*=TP;L^=la,R^=la,a^=la,b^=la,l^=la,r^=la,X^=la,x^=la;
slv(T,L,R,a,b,l,r,x);
printf("%u\n",la=m0.a00^R1);
if(T==rp[be[T]])bud(be[T]);
}
return 0;
}
时间复杂度 \(O(\frac{m}{B}B\log B+mB+m\frac{m}{B}\log B)\)，取 \(B=\frac{\sqrt{2}}{2}m{\log m}\) 时为 \(O(m\sqrt{m\log m})\)，空间复杂度 \(O(m)\)。常数较小，精细实现可以 AC
分散层叠优化分块
显然复杂度瓶颈在于块内二分，是分散层叠的经典应用。
块内排序部分可以手写基数排序，不过 std::sort 足以轻松通过。由于博主不熟悉分散层叠，因此代码仍有卡常空间
code
const int N = 3e5+5, B = 800, BN = N/B+5;
int n,m,type,L[N],R[N],a[N],b[N],ql,qr,X,in[N];
U lstans,ans1,ans2;
VI t[BN],mx[BN];
vector aa[BN],bb[BN];
struct Node {
int x,pos,nxt;
Node(int x=0,int pos=0,int nxt=0):x(x),pos(pos),nxt(nxt){}
friend bool operator < (Node a,Node b) { return a.x < b.x; }
}; vector li[BN];
int rd() { LL x; read(x); return type ? x^lstans : x; }
void build(int i) {
int l = (i-1)*B+1, r = i*B;
For(j,l,r) t[i].pb(L[j]), t[i].pb(R[j]); t[i].pb(0), t[i].pb(n+1);
sort(all(t[i])), t[i].erase(unique(all(t[i])),t[i].end());
aa[i].assign(sz(t[i]),1), bb[i].resize(sz(t[i])), mx[i].resize(sz(t[i]));
For(j,l,r) Rep(k,0,sz(t[i])) if( L[j] < t[i][k] && t[i][k] <= R[j] )
aa[i][k] = (LL)aa[i][k] * a[j] %mod,
bb[i][k] = ((LL)a[j] * bb[i][k] + b[j]) %mod,
ckmax(mx[i][k],b[j]);
if( i == 1 )
For(j,0,sz(t[1])) li[1].pb(t[1][j],j,0);
else {
vector tmp;
Rep(j,0,sz(li[i-1])-1) if( (j & 1) ) tmp.pb(li[i-1][j].x,0,j);
tmp.pb(n+1,0,sz(li[i-1])-1);
Rep(j,0,sz(t[i]), k = 0) {
while( k < sz(tmp)-1 && tmp[k].x <= t[i][j] )
li[i].pb(tmp[k].x,j,tmp[k].nxt), ++k;
li[i].pb(t[i][j],j,tmp[k].nxt);
}
}
}
void bf(int l,int r) {
For(i,l,r) if( L[i] < X && X <= R[i] )
ans1 = ((LL)a[i]*ans1+b[i]) %mod, ckmax(ans2,b[i]);
}
void query(int l,int r) {
static int tp,stk[N];
int j = lower_bound(all(li[r]),Node(X,0,0))-li[r].begin();
stk[++tp] = li[r][j].pos;
rFor(i,r-1,l) {
j = li[i+1][j].nxt;
while( li[i][j-1].x >= X ) --j;
stk[++tp] = li[i][j].pos;
}
for(; tp; --tp)
ans1 = ((LL)aa[r-tp+1][stk[tp]] * ans1 + bb[r-tp+1][stk[tp]]) %mod,
ckmax(ans2,mx[r-tp+1][stk[tp]]);
}
signed main() { freopen("dark.in","r",stdin); freopen("dark.out","w",stdout);
read(n,m,type);
For(i,1,m) in[i] = (i-1)/B+1;
For(i,1,m) {
L[i] = rd()-1, R[i] = rd(), a[i] = rd(), b[i] = rd(), ql = rd(), qr = rd();
X = rd(), ans1 = rd(), ans2 = 0;
if( in[ql]+1 >= in[qr] ) bf(ql,qr);
else {
int l = (ql-1)/B+1, r = (qr-1)/B+1;
bf(ql,l*B), query(l+1,r-1), bf((r-1)*B+1,qr);
}
write(lstans=ans1^ans2);
if( in[i] != in[i+1] ) build(in[i]);
}
return ocl();
}
时间复杂度 \(O(m\sqrt{m})\)，空间复杂度 \(O(m)\)，常数原因并没有快很多，不过难写很多
标算
zsy 说 std 是单 \(\log\) 的，让我们一起膜拜他
upd：找到一份看上去时空都是单 \(\log\) 的代码，并没有看懂，因此我建议空间 128M
by Cirno_9
#include
#define pbk emplace_back
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(int i=a,i##i=b;i>=i##i;--i)
#define mid ((l+r)>>1)
#define lc k<<1
#define rc lc|1
using namespace std;
typedef long long ll;
const ll N=1050010,P=2677114440;
ll n,m,typ,ans,L,R,a,b,ql,qr,X,x,S=1;
namespace Reimu{
char buf[1<<20],obuf[1<<20],*p1,*p2,*p3=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline ll read(){
ll x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
return x;
}
inline void get(ll& x){x=read()^(typ?ans:0);}
templatevoid get(T&A,Ts&...As){get(A),get(As...);}
inline void write(ll x){
static char buf[15];
static int len=-1;
do buf[++len]=x%10+48,x/=10;while(x);
while(len>=0)putchar(buf[len]),--len;
putchar('\n');
}
inline void flush(){fwrite(obuf,p3-obuf,1,stdout),exit(0);}
#undef getchar
#undef putchar
}using namespace Reimu;
/*-------------------- Read & Write --------------------*/
struct zzy{
ll a,b,mx;
int l,r;
zzy operator+(zzy p){return {a*p.a%P,(b*p.a+p.b)%P,max(mx,p.mx),max(l,p.l),min(r,p.r)};}
bool operator<(zzy p)const{return rf[N];
void Mg(int k){
int sl=f[lc].size(),sr=f[rc].size();
f[k].reserve(sl+sr);
for(int i=0,j=0,E,R;i=f[rc][j].r;
}
}
zzy find(vector&a,int h){return a[lower_bound(a.begin(),a.end(),(zzy){0,0,0,0,h})-a.begin()];}
zzy qry(int k=1,int l=1,int r=S){
if(l>qr||r=ql&&r<=qr)return find(f[k],X);
return qry(lc,l,mid)+qry(rc,mid+1,r);
}
signed main(){
freopen("dark.in","r",stdin);
freopen("dark.out","w",stdout);
for(get(n,m,typ);S 卡常
- 模数在
unsigned范围内，不需要long long - 使用全局变量代替参数传递
- 不要用矩阵乘法
其他点标在代码里了
后记
题目非常经典，做法也很多，但在如何抉择上值得一想，也不失为锻炼码力的好机会
波波给看了伊藤美诚 \(10:7\) 被逆转的视频，其心态变化很像昨天考场上做该题的我，自己确实没注意，当作『知识』学习吧
做题和考场状态真的差很多，今早用了 1.5h 才写出内层平衡树（虽然也有板子不熟的缘故），也算是历史遗留问题了，希望能尽快克服