5 条题解

  • 2
    @ 2026-9-27 14:15:45 
    #include<iostream>
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math,no-stack-protector")
#pragma GCC target("sse,sse2,avx,avx2,bmi,bmi2,lzcnt,popcnt,avx512vl,avx512f,tune=native")
#define chmax(a,b) (a<b?a=b:0)
const int mod=998244353;
int n,q,V,st[1050010][21],lg2[1050010];
#define Tp template<typename T>
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void read(T& x){
    x=0;char c=getchar();bool f=0;
    for(;!isdigit(c);c=getchar())if(c=='-')f=1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    f&&(x=-x);
}
template<typename T>void qw(T x)
{
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}	
int main(){
	read(n);read(q);read(V);
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;i++)st[i][0]=1;
	int l,r,v,d;
	for(int _=1;_<=q;_++){
		read(l);read(r);read(v);
		d=lg2[r-l+1];
		chmax(st[l][d],v);
		chmax(st[r-(1<<d)+1][d],v);
	}
	for(int i=20;i>=1;i--){
		for(int x=1;x+(1<<i)-1<=n;x++){
			chmax(st[x][i-1],st[x][i]);
			chmax(st[x+(1<<i-1)][i-1],st[x][i]);
		}
	}
	long long ans=1;
	for(int i=1;i<=n;i++)ans=ans*(V-st[i][0]+1)%mod;
	qw(ans);
	return 0;
}
    • 2
      @ 2026-9-27 11:48:15

      Hollow Knight:SilkSong 题解

      注意：本题卡常级为严重。

      本题难度：绿

      致歉：我们应该放一个快读模板的。

      显然，q≤107q\le 10^7 的数据明显不是让线段树过的，所以我们需要一种能够 O(1)O(1) 处理一组修改的数据结构。

      注意到本题支持离线，我们考虑处理完所有询问之后再去统一处理，于是我们需要一种打 tag 十分方便，每一次修改至多只需要修改常数级的区间。注意到这种修改满足可重性（也就是一个区间可以被操作多次），所以在这里，我们借用区间并查集的思想，使用倍增解决该问题。

      定义 sti,jst_{i,j} 为从 ii 开始为长度为 2j2^j 个数打上 sti,jst_{i,j} 的标签，最后全部按照 jj 从大到小的顺序下传。

      代码：

      #include<bits/stdc++.h>
#define chmax(a,b) (a<b?a=b:0)
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,q,V;
int st[1000010][21],lg2[1000010];
#define Tp template<typename T>
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void read(T& x){
    x=0;char c=getchar();bool f=0;
    for(;!isdigit(c);c=getchar())if(c=='-')f=1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    f&&(x=-x);
}
template<typename T>void qw(T x)
{
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}	
int main(){
	read(n);read(q);read(V);
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;i++)st[i][0]=1;
	int l,r,v;
	while(q--){
		read(l);read(r);read(v);
		int d=lg2[r-l+1];
		chmax(st[l][d],v);
		chmax(st[r-(1<<d)+1][d],v);
	}
	for(int i=20;i>=1;i--){
		for(int x=1;x+(1<<i)-1<=n;x++){
			chmax(st[x][i-1],st[x][i]);
			chmax(st[x+(1<<i-1)][i-1],st[x][i]);
		}
	}
	ll ans=1;
	for(int i=1;i<=n;i++)ans=ans*(V-st[i][0]+1)%mod;
	qw(ans);
	return 0;
}

      这个故事告诉我们，st 表并不是不支持修改，只是没法在线罢了。

      同思路的题：双倍经验（甚至这个 idea 就是这么来的）

      • 1
        @ 2026-9-27 15:36:14

        发个福利。 峰值1173ms

        #include<bits/stdc++.h>
#include<iostream>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math,no-stack-protector")
#pragma GCC target("sse,sse2,avx,avx2,bmi,bmi2,lzcnt,popcnt,avx512vl,avx512f,tune=native")
#define mx(a,b) (a<b?a=b:0)
const int N=1e6+10,P=998244353;
int st[N][21],lg2[N];
namespace FastIO
{
    constexpr int Buf=1<<20;
    char ibuf[Buf],*ip=ibuf,*ie=ibuf;
    char obuf[Buf],*op=obuf;
    inline char gc()
    {
        if(ip==ie)ie=(ip=ibuf)+fread(ibuf,1,Buf,stdin);
        return ip==ie?EOF:*ip++;
    }
    template<typename T>inline void rd(T &x)
    {
        x=0;int f=1;char c=gc();
        for(;c<'0'||c>'9';c=gc())
        {
            if(c=='-')f=-1;
            if(c==EOF)return;
        }
        for(;c>='0'&&c<='9';c=gc())x=x*10+(c^48);
        x*=f;
    }
    inline void flush(){fwrite(obuf,1,op-obuf,stdout);op=obuf;}
    template<typename T>inline void wt(T x)
    {
        if(op+32>=obuf+Buf)flush();
        if(x<0){*op++='-';x=-x;}
        char tmp[32];int p=0;
        if(!x)tmp[p++]='0';
        for(;x;x/=10)tmp[p++]=(x%10)^48;
        while(p--)*op++=tmp[p];
    }
    inline void wc(char c){if(op==obuf+Buf)flush();*op++=c;}
}
using namespace FastIO;
int main()
{
	int n,q,v;rd(n);rd(q);rd(v);
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;i++)st[i][0]=1;
	for(int i=1,l,r,x;i<=q;i++)
	{
		rd(l);rd(r);rd(x);
		int d=lg2[r-l+1];
		mx(st[l][d],x);
		mx(st[r-(1<<d)+1][d],x);
	}
	for(int i=20;i>=1;i--)
	{
		for(int x=1;x+(1<<i)-1<=n;x++)
		{
			mx(st[x][i-1],st[x][i]);
			mx(st[x+(1<<(i-1))][i-1],st[x][i]);
		}
	}
	long long ans=1;
	for(int i=1;i<=n;i++)ans=ans*(v-st[i][0]+1)%P;
	wt(ans);flush();return 0;
}
        • 1
          @ 2026-9-27 14:46:07

          O(3)O(3)优化是神！！！！！！

          标程还要靠运气

          峰值时间1500多ms1500多ms

          #include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
#define ll long long
#define chmax(a,b) (a<b?a=b:0)
#define Tp template<typename T>
char buf[1<<20],*p1=buf,*p2=buf;
const ll P=998244353;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void qr(T& x)
{
    x=0;char c=getchar();bool f=0;
    for(;!isdigit(c);c=getchar())if(c=='-')f=1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    f&&(x=-x);
}
template<typename T>void qw(T x)
{
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}
ll n,q,V,l,r,x,st[1000010][21],lg2[1000010];
int main()
{
	qr(n);qr(q);qr(V);
	for(ll i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(ll i=1;i<=n;i++)st[i][0]=1;
	while(q--)
	{
		qr(l);qr(r);qr(x);
		ll d=lg2[r-l+1];
		chmax(st[l][d],x);
		chmax(st[r-(1<<d)+1][d],x);
	}
	for(ll i=20;i;i--)
	{
		for(ll x=1;x+(1<<i)-1<=n;x++)
		{
			chmax(st[x][i-1],st[x][i]);
			chmax(st[x+(1<<i-1)][i-1],st[x][i]);
		}
	}
	ll ans=1;
	for(ll i=1;i<=n;i++)ans=ans*(V-st[i][0]+1)%P;
	qw(ans);
	return 0;
}
          • 0
            @ 2026-9-27 16:27:47

            参和一手

            #include<bits/stdc++.h>
#define chmax(a,b) (a<b?a=b:0)
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,q,V;
int st[1000010][21],lg2[1000010];
#define Tp template<typename T>
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void read(T& x){
    x=0;char c=getchar();bool f=0;
    for(;!isdigit(c);c=getchar())if(c=='-')f=1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    f&&(x=-x);
}
template<typename T>void qw(T x)
{
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}	
int main(){
	read(n);read(q);read(V);
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;i++)st[i][0]=1;
	int l,r,v;
	while(q--){
		read(l);read(r);read(v);
		int d=lg2[r-l+1];
		chmax(st[l][d],v);
		chmax(st[r-(1<<d)+1][d],v);
	}
	for(int i=20;i>=1;i--){
		for(int x=1;x+(1<<i)-1<=n;x++){
			chmax(st[x][i-1],st[x][i]);
			chmax(st[x+(1<<i-1)][i-1],st[x][i]);
		}
	}
	ll ans=1;
	for(int i=1;i<=n;i++)ans=ans*(V-st[i][0]+1)%mod;
	qw(ans);
	return 0;
}
            • 1

            Hollow Knight:SilkSong

            信息

            ID
            12700
            时间
            2000ms
            内存
            512MiB
            难度
            9
            标签
            (无)
            递交数
            192
            已通过
            15
            上传者
            1. Language
            2. 兼容模式
            3. 主题
            3. Worker 0, 6ms
            4. Powered by Hydro v5.0.7 Community