SBC的水题大赛题解

犇犇犇犇 · 2020-03-29 20:26:35 · 个人记录

比赛链接

T1 小镇题解

对于 30\% 的数据，1 \leq n,k \leq 100。

没啥注意的，算法同 80\% 的数据，直接根据题意暴力模拟即可。

对于 80\% 的数据，1 \leq n,k \leq 5000。

我们可以暴力枚举任意两个被涂色的格子，看他们是否相邻。
对于两个相邻的格子，可以注意到他们行相同，列差为一或者列相同，行差为一。所以我们可以通过 abs(x_1-x_2)+abs(y_1-y_2)==1的方法来判断是否相邻。
时间复杂度 O(k^2)。
代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
int n,k,x[MAXN],y[MAXN],ans=0;
int main()
{
    n=read();k=read();
    for(int i=1;i<=k;i++)
    {
        x[i]=read();
        y[i]=read(); //读入
    }
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k;j++) //暴力枚举任意两个格子
        {
            if(abs(x[i]-x[j])+abs(y[i]-y[j])==1) //判断相邻
                ans++;
        }
    cout<<ans<<endl;
    return 0;
}

对于 100\% 的数据，1 \leq n,k \leq 10^5。

我们把两个相邻格子的公共边成为夹边。
观察样例，可以发现对于每条夹边，都平行于x轴或者平行于y轴。所以我们可以自然想到对于平行于x轴和y轴的夹边分开计算。
接下去步骤就比较明了了，对于平行于x轴的边，我们把格子的x轴作为第一关键字排序，再根据y轴排序。
这样，就保证了相邻的两个格子如果x轴相同，那他们的y轴单调递增。
这时候我们比较y轴是否差一，便能统计出所有平行于x轴的夹边了。平行于y轴的边同理，具体见代码。
时间复杂度 O(k log k)

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int x,y;
}a[MAXN];
bool cmp1(node a,node b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y; 
} 
bool cmp2(node a,node b)
{
    if(a.y!=b.y) return a.y<b.y;
    else return a.x<b.x;
} //排序函数
int n,k,ans;
int main()
{
    n=read();k=read();
    for(int i=1;i<=k;i++)
    {
        int x,y;
        x=read();y=read();
        a[i].x=x;a[i].y=y;      
    }
    sort(a+1,a+k+1,cmp1); //统计平行于x轴的边
    for(int i=1;i<k;i++)
    {
        if(a[i].x==a[i+1].x && a[i].y==a[i+1].y-1) //若x轴相同并且y轴差为1
            ans++;
    }
    sort(a+1,a+k+1,cmp2); //统计平行于y轴的边
    for(int i=1;i<k;i++)
    {
        if(a[i].y==a[i+1].y && a[i].x==a[i+1].x-1) //同上
            ans++;
    }
    cout<<ans<<endl;
    return 0; //qwq
}

T2 时光的流逝题解

这道题其实本质就是个图上的博弈论

对于 10\% 的数据，保证图是一条链。

由于是一条链，所以情况是唯一的，直接链表模拟即可。具体见代码。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,q,nxt[500005],a,b;
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        nxt[a]=b; //由于是链表
    }
    for(int i=1;i<=q;i++)
    {
        cin>>a>>b;
        int k=-1,x=a,f=0; //x表示当前位置，k表示当前走棋的人
        while(nxt[x])
        {
            k=-k; //每次转换走棋的人
            x=nxt[x]; //走到下一个位置
            if(x==b) //到终点
            {
                cout<<k<<endl;
                f=1;
                break;
            }
        }
        if(!f)
            cout<<k<<endl; //如果走到终点，则无法动的人输
    }
    return 0;
}

不难发现这个题是个图上的博弈论的问题。我们自然可以考虑到在图上标记必胜点以及必败点。
首先终点为必败点，所有出度为0的点均为必败点，然后所有能一步到达必败点的点为必胜点，下一步只能到必胜点的点为必败点。于是我们便可以根据这个规则给所有点标记，最后如果起点没有标到，那么就平局。

给张图理解下：这里有一张图，终点为 10，我们从终点开始判断起点的情况。其中必败点标记为红色，必胜点标记为蓝色。

首先，终点10为必败点。9,5能到达10，所以9，5为必胜点。
7，4由于是死路（及走到这个点无路可走）为必败点，标记为红色，于是3，6能到达4，7，故为必胜点。
8能到达的所有点(6)均为必胜点，所以8为必败点。
1能到达必败点8，所以1为必胜点。
2能到达的所有点(1)均为必胜点，所以2为必败点。
这样我们就能得到所有起点的情况了。

对于 50\% 的数据，1\leq n\leq 10^3，1\leq m\leq 2\times10^3，1\leq q\leq 10。

这一档主要就是对于上面那种方法比较暴力的解决方法。每次暴力枚举所有点，看看是否能更新，知道不能更新为止。复杂度 O(qn^2)

对于 70\% 的数据，1\leq n\leq 10^5，1\leq m\leq 2\times10^5，1\leq q\leq 10。

这一档就是给一些常数比较大的做法，或者是一些玄学带 log 做法的做法。比如用优先队列判断度数最小的点以及，起点终点搜两遍的做法。

对于 100\% 的数据，1\leq n\leq 10^5，1\leq m\leq 5\times10^5，1\leq q\leq 500。

我们可以发现只要一个点的所有出点的状态（即确定是否为必胜点或必败点）时，那个点的状态我们便能确定。因为若它有一条边指向必败点，则它为必胜点。若它所有边都指向必胜点，那么他就是必败点。所以我们就能想到然后建反向边（因为我们需要从已经确定的点去修改未知的点，即需要知道哪些点会通到它），用一个数组记录它的出度，一个数组记录当前的标记（必胜点或必败点）。
我们用一个队列保存当前可以确定状态的点（即出度为0的点，由于我们只需要讨论反向边的图，所以这里出度即为原图的入度），如果找到一个必败点，那么立即修改所有能通到它的点，把这些点标记为必胜点，并且将能通到这些必胜点的点出度减一。同时我们在减去出度的时候看出度是否为0，如果为0，那么这个点的状态即可确定，放进队列。相当于将已经确定状态的点从图中删去。时间复杂度 O(qm)

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+5;
const int MAXM = 5e5+5;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
int n,m;
int p[MAXN],vic[MAXN],out[MAXN];
int cnt,head[MAXM],f[MAXN],d[MAXN];
struct edge
{
    int v,nxt;
}e[MAXM*2];
inline void addedge(int u,int v)
{
    cnt++;
    e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
queue<int> q;
void del(int u)
{
    f[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        d[v]--;
        if(d[v]==0)
            q.push(v);
    }   
} //当前点已经确定状态点删去
int main()
{
    int Q;
    n=read();m=read();Q=read();
    for(int i=1;i<=m;i++)
    {
        int a,b;
        a=read();b=read();
        addedge(b,a); //建反向边
        p[a]++;  //入度
        out[b]++; //出度
    }
    while(Q--)
    {
        int x,y;
        while(!q.empty()) q.pop();
        x=read();y=read();
        memset(f,0,sizeof(f)); 
        memset(d,0,sizeof(d));
        memset(vic,0,sizeof(vic)); //初始化
        for(int i=1;i<=n;i++)
        {
            d[i]=p[i];
            if(p[i]==0) 
                q.push(i); //若当前点出度为0，放进队列
        } 
        q.push(y); //将终点放进队列
        vic[y]=1; //终点为必败点
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            if(f[u]==1) 
                continue; //已经被访问过
            if(vic[x]!=0)
                break; //小优化，若起点状态已经确定，那就不需要继续搜索了
            del(u); //u已经能确定状态了，将它删去
            if(vic[u]==1)//如果u为必败点，那么所有能通往它的点为必胜点  
            {
                for(int i=head[u];i;i=e[i].nxt) 
                {
                    int v=e[i].v;
                    if(vic[v]==0)
                    {
                        vic[v]=-1;
                        del(v); //v为必胜点，状态确定，将它删去
                    }
                }   
            }
            else if(out[u]==0)
            {
                vic[u]=1; //若u在原图出度为0，则为必败点
            }
            else //u状态未确定
            {
                vic[u]=1; //u能走到的所有点为必胜点，u为必败点
                for(int i=head[u];i;i=e[i].nxt) //将所有能通到必败点标为必胜点
                {
                    int v=e[i].v;
                    if(vic[v]==0)
                    {
                        vic[v]=-1;
                        del(v); //删去
                    }
                }       
            }       
        }
        cout<<-vic[x]<<endl; //输出起点状态
    }
    return 0;
}

T3 人题解

Subtask 1 (10\%)，1 \le T \le 10, 1 \le a,b \le m \le 10。

对于这一部分，T,a,b 都很小，所以我们可以考虑暴力枚举所有的可能情况。枚举从所有奇数中选 a 个，在 m 个偶数中选 b 个。一个 \operatorname{dfs} 即可

代码：

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int Q,m,a,b,ans,l[105],r[105]; 
//l数组表示奇数已经选取的数字，r数组表示偶数已经选取的数字
bool vis[105]; //保存当前数字是否可用
void dfs(int m,int x,int y)
{
    if(x==a+1 && y==b+1) //如果已经选完了
    {
        ans++; 
        return;
    }
    if(x==a+1) //如果奇数选完了，选偶数
    {
        for(int i=r[y-1]/2+1;i<=m;i++) //从上一次选的地方开始选
        {
            if(vis[2*i]==0) //当前数可用
            {
                vis[2*i]=1;
                r[y]=i*2; //记录
                dfs(m,x,y+1); //dfs下一层
                vis[2*i]=0; //回溯
            }
        }
    }
    else //选奇数
    {
        for(int i=l[x-1]/2;i<m;i++) 
        {
            if(vis[2*i+1]==0) //同上
            {
                vis[2*i]=vis[2*i+1]=vis[2*i+2]=1; //由于不能选相邻的数，则2*i+1周围的数也不能选
                l[x]=i*2+1;
                dfs(m,x+1,y);
                vis[2*i+1]=0; //回溯
                if(i==0 || vis[2*i-1]==0) //如果2*i左右两边都没有数，她才可以继续使用
                    vis[2*i]=0;
                if(vis[2*i+3]==0) //此时2*i+1不选，如果2*i+3也不选，那么2*i+2可以使用
                    vis[2*i+2]=0;
            }
        }
    }
}
int main()
{
    Q=read();
    while(Q--)
    {
        m=read();a=read();b=read();
        memset(vis,0,sizeof(vis)); //初始化
        ans=0;
        dfs(m,1,1);
        cout<<ans<<endl;
    }
    return 0;
}

Subtask 2 (40\%)，1 \le T \le 10^6, 1 \le a,b \le m \le 100。

我们可以发现 T 很大，但是 m,a,b 很小。提示已经很明确了，我们可以预先用一个3维数组保存每一个 m,a,b 的答案，然后每次询问直接输出，每次询问复杂度O(1)
我们用 dp[m][a][b] 保存答案。m,a,b 与题目中相同。我们希望从 dp[m-1][a][b] 推出 dp[m][a][b]
对于 1 到 2m 中有选 a 个奇数，b 个偶数，我们可以分为3种情况

在1到2(m-1)中选a个奇数，b个偶数。此时答案为dp[m-1][a][b]
在1到2(m-1)中选a个奇数，b-1个偶数，在 2m-1,2m 中选 2m 这个偶数。此时答案为 dp[m-1][a][b-1]
在1到2(m-1)中选a-1个奇数，b个偶数，在 2m-1,2m 中选 2m-1 这个奇数。此时情况数为 dp[m-1][a-1][b]。但是这里还有另外一个条件，因为我们选了 2m-1 , 也就是说 2m-2 这个数我们不能选。所以我们需要把选了 2m-2 的情况排除掉。也就是说排除前 2m-2 个数中选了 2m-2 的情况。此时前 2m-4 个数可以随便选，所以情况为 dp[m-2][a-1][b-1]。所以这种情况最终的答案为 dp[m-1][a-1][b]-dp[m-2][a-1][b-1]

所以我们可以得到递推式子

dp[m][a][b]=dp[m-1][a][b]+dp[m-1][a-1][b]+dp[m-1][a][b-1]-dp[m-2][a-1][b-1]

初始化时，dp[i][0][j]=dp[i][j][o]=C_i^j （此处C表示组合数）

最后，别忘了取模，别忘了 $\operatorname{long}\ \operatorname{long}

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXM = 105;
const ll MOD = 998244353;
inline ll read()
{
    ll x=0,f=1;char c=getchar(); 
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
} 
ll dp[MAXM][MAXM][MAXM];
int main()
{
    ll T;
    T=read();
    dp[1][0][0]=dp[1][1][0]=dp[1][0][1]=1;
    dp[2][1][1]=1; //初始化
    for(ll i=2;i<=100;i++)
    {
        dp[i][0][0]=1;
        for(ll j=1;j<=i;j++) 
        {
            dp[i][0][j]=(dp[i-1][0][j]+dp[i-1][0][j-1])%MOD;
            dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j-1][0])%MOD;
        //dp[i][0][j]=dp[i][j][o]=C(i,j) 这里我用了递推实现，C(i,j)=C(i-1,j)+C(i-1,j-1)
        }
    }
    for(ll i=3;i<=100;i++)
    {
        for(ll a=1;a<=100;a++)
        {
            for(ll b=1;a+b<=i;b++)
            {
                dp[i][a][b]=(dp[i-1][a][b]+dp[i-1][a-1][b]+dp[i-1][a][b-1]-dp[i-2][a-1][b-1]+MOD)%MOD; //dp,这里如果不加+MOD再%MOD可能会出现负数的情况
            }
        }
    }
    while(T--)
    {
        ll m,a,b;
        m=read();
        a=read();
        b=read();
        cout<<dp[m][a][b]<<endl; //每次询问O(1)
    }
    return 0;
}

Subtask 3 (50\%)，1 \le T \le 10^6, 1 \le a,b \le m \le 10^6。

我们发现 T,a,b 都很大，明显是推公式，O(m) 预处理，每次询问 O(1)
观察数据，我们可以发现 dp[m][i][j]=C_{m-i}^j \times C_{m-j}^i

下面我们来证明一下。需要用到组合数性质

C_n^k=C_{n-1}^k \times C_{n-1}^{k-1}

C_n^k=C_{n+1}^k-C_n^{k-1}

上一个子问题，我们得到递推公式

dp[m][a][b]=dp[m-1][a][b]+dp[m-1][a-1][b]+dp[m-1][a][b-1]-dp[m-2][a-1][b-1]

显然，当 a,b 中有一个数为 0 的时候成立。
对 dp[2][1][1] 成立。
我们将公式带入右边。

\large\texttt{ }\texttt{ }\texttt{ }\texttt{ }\texttt{ }C_{m-a-1}^{b} \times C_{m-b-1}^{a}+C_{m-a}^{b} \times C_{m-b-1}^{a-1}+C_{m-a-1}^{b-1} \times C_{m-b}^{a}-C_{m-a-1}^{b-1} \times C_{m-b-1}^{a-1}

\large =C_{m-a-1}^{b} \times C_{m-b-1}^{a}+C_{m-b-1}^{a-1} \times (C_{m-a}^{b}-C_{m-a-1}^{b-1})+C_{m-a-1}^{b-1} \times C_{m-b}^{a}

\large =C_{m-a-1}^{b} \times C_{m-b-1}^{a}+C_{m-b-1}^{a-1} \times C_{m-a-1}^{b}+C_{m-a-1}^{b-1} \times C_{m-b}^{a}

\large =C_{m-a-1}^{b} \times (C_{m-b-1}^{a}+C_{m-b-1}^{a-1})+C_{m-a-1}^{b-1} \times C_{m-b}^{a}

\large =C_{m-a-1}^{b} \times C_{m-b}^{a}+C_{m-a-1}^{b-1} \times C_{m-b}^{a}

\large =C_{m-b}^{a} \times (C_{m-a-1}^{b}+C_{m-a-1}^{b-1})

\large =C_{m-b}^{a} \times C_{m-a}^{b}

所以我们就证明了这个结论。对于每个问题，我们只需要求出 C_{m-b}^{a} \times C_{m-a}^{b} 即可。

求组合数的办法我用的是线性预处理逆元，不了解的可以看这里

组合数C_a^b mod p 相当于是 a!/(a-b)!/b! mod p。这里 p 是质数，所以除以 p 等于乘上在模 p 下的逆元。所以我们只要预处理出每个数的阶乘在模 p 下的逆元即可。
若 a[i] 表示 i! mod p， ny[i] 表示 i! 的逆元 mod p , 则C_{m-s}^t即等于a[m-s]\times ny[n-t-s] \times ny[t]。

别忘了 \operatorname{long}\ \operatorname{long}
代码：

#include <bits/stdc++.h>
#define ll long long
const int MAXN = 1e6+5;
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
const ll MOD = 998244353;
ll a[MAXN],ny[MAXN],Q,n,t,s;
ll ans,d,e,f,g,h;
int main()
{
    Q=read();
    a[0]=1;
    ny[1]=1;
    for(int i=1;i<MAXN;i++)
        a[i]=((ll)i*a[i-1])%MOD;
    for(int i=2;i<MAXN;i++)
        ny[i]=((ll)(MOD-MOD/i)*ny[MOD%i]%MOD);
    for(int i=2;i<MAXN;i++)
        ny[i]=ny[i]*ny[i-1]%MOD; //预处理逆元
    while(Q--)
    {
        n=read();t=read();s=read();
        if(n==t+s)
        {
            printf("1\n");
            continue;
        } //如果n=t+s那么只有一种情况
        ans=a[n-s]*a[n-t]%MOD;
        ans=ans*ny[t]%MOD;ans=ans*ny[s]%MOD;
        ans=ans*ny[n-t-s]%MOD;ans=ans*ny[n-t-s]%MOD; //求组合数
        printf("%lld\n",ans);
    }
    return 0;
}

T4　归家之路　题解

令序列长 m=2^n。

首先对于前 5\% 的数据可以直接暴力。复杂度 O(mq)。

暴力枚举子集的方法是（这里是 c++ 代码）

int f=x^y;
for(int t=x^y;t>=0;t=(t-1)&f)

当然还有什么都不发生的情况，也就是不存在满足要求的 c。这个可以使用 a and b=a 进行特判。

继续开始思考后面的部分分。之后都假设所有的修改和询问都是有效的，也就是 a and b=a一直成立。

这个修改、询问的形式类似一个区间，那么需要知道一个前置知识 高维前缀和。如果不知道的话可以学一下，比较简单。

那么类比不带修直接求区间的值，我们考虑用几个高维前缀和相加减去表示一个询问的答案。

这里可以从简单的情况开始考虑。如果 a=0，那么就直接是一个高维前缀和的答案；那么继续考虑，令 sum(i) 为 i 的高维前缀和，如果 a=1，那么询问 (a,b) 的答案是一些 a_c 的和，其中 c 是奇数并且 c and b=b。那么这个答案比 sum(b) 小了 c 是偶数，并且 c and b=b 的位数之和。后面的那个恰好可以用 sum(b-1) 表示。

思路逐渐明朗起来，如果 x 是 b 与 a 相同且二进制位 1 的一位的值，那么我们可以得到

query(a,b)=query(a-x,b)-query(a-x,b-x)

这个式子可以位运算进行优化，x=a&-a，a-x 可以用 a^x 表示。

这个看似还没啥用——如果 a,b 相同那么这个复杂度还是 m 级别的。但是仔细分析：

如果 a,b 二进制不同的位有 x 位，相同的有 y 位，其中 x+y=n，那么直接暴力计算就可以用 O(2^x) 次计算完成；如果用上面那种方法，它的复杂度是 O(2^y)。

进行特判并且选择可以做到 O(2^{\min(x,y)})，也就是单次询问 O(\sqrt m)。这个算法可以通过第二档部分分。

这里有一个很小的优化，没什么用：

可以快速预处理出 0 到(2^n-1) 中每一个数有多少个二进制 1，这样查询二进制 1 的个数就从 O(\log m) 变成了 O(1)。具体实现和 FFT 中的那个 rev 数组类似：

for(int i=0;i<(1<<n);i++)count[i]=count[i>>1]+(i&1),rev[i]=(1<<n)-i-1;

其实这么进行修改也是 O(\sqrt m) 的，但是唯一的问题就是无法及时更新。如果询问都在修改后面，可以考虑懒标记，用数组 curr 记录。如果 curr[i] 记录了值，那么就代表所有 i 的子集都要加上这个值。

这里用代码更清楚一点：

void modify(int x,int y,uint z)
{
    if(count[x^y]<=n/2)
    {
        int f=x^y;
        for(int t=x^y;;t=(t-1)&f){
            a[t|x]+=z;
            if(t==0)
                break;
          //这一部分是对修改值不多的情况进行暴力
        }
        return;
    }
    if(x==0)
    {
        curr[y]+=z;//如果x=0那么就可以直接打上懒标记
        return;
    }
    int lbt=x&-x;
    modify(x^lbt,y,z);
    modify(x^lbt,y^lbt,-z);//与 query 部分类似的递归
}

等到所有修改结束后可以下放懒标记，暴力下放的复杂度是 O(3^n)，总时间复杂度 O(\sqrt mq+3^n)，可以通过第三档部分分。

然而这里并不是没有优化的空间了。下放懒标记的过程完全可以看成又一次高维前缀和。

本来的高维前缀和上的值是它的所有子集的和；而这时候需要加的值，是所有以它为自己的懒标记的和。

举个栗子，如果一个数的二进制表示是 001，那么高维前缀和中就是 000,001 的和，在这种情况下要加上 001,011,101,111 这四个懒标记的和。所以这样只用反着来一遍高维前缀和就行了。

为了加速，我预处理了 rev 数组代表一个数二进制取反后的结果，因为这里不能直接用 ~。（这个 rev 不是 FFT 中的 rev）

话不多说上代码：

void update()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
        {
            if(j&(1<<i))
                curr[rev[j]]+=curr[rev[j^(1<<i)]];
        }
  //这里是反着的高维前缀和
    for(int i=0;i<(1<<n);i++)
        a[i]+=curr[i];
    for(int i=0;i<(1<<n);i++)
        pres[i]=a[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
            if(j&(1<<i))
                pres[j]+=pres[j^(1<<i)];
}

其中 pres 是高维前缀和数组。这一次 update 的复杂度是高维前缀和的复杂度 O(n2^n)。

好了，各位大佬们看到这里，正解已经呼之欲出了：分块！

我们假设块长为 s，一共 t 块。

修改还是正常修改，查询还是正常查询。这里复杂度是 O(q \sqrt m)。

查询的时候，唯一的问题就是计算块内贡献。这个可以位运算 O(1) 计算每个贡献，复杂度是 ms；每一块的 update 的复杂度是 O(tn2^n)，那么我们可以得到总的复杂度可以达到 O(m \sqrt {nq}+q \sqrt m)，在块长为 \sqrt{nq} 时最优。

块内的贡献还是有细节的。大概是这两种情况：

（1）一个修改的数和询问的数没有相同的。

（2）有一部分相同。

这个位运算有很多种实现方法，直接上代码：

for(int i=1;i<=cnt;i++)
            {
                num=(s[i].a|a)&(s[i].b&b);
                if(num==int(s[i].a|a))
                {
                    num=(s[i].a|a)^(s[i].b&b);
                    ans+=(1<<count[num])*s[i].k;
                }
            }
            cout<<ans<<endl;

std 的长度 2235byte，作为数据结构还是比较良心的。

T5 一直在你身旁题解

首先有个 n^3 的暴力。假设 dp_{l,r} 为确定答案在区间 [l,r] 后需要的最小代价，那么可以得到式子：

dp_{i,j}=\min_{i<k<j}\max\{dp_{i,k},dp_{k+1,j}\}+a_k

枚举区间长度，或者倒序枚举 i 都可以在 n^3 的时间复杂度完成。

考虑优化，爆推式子好像有点难，那么观察式子，里面有一个 \max 和一个 \min，考虑先拆开里面的 \max，也就是对于每一个 (i,j) 对子，找到一个最小的 k=f(i,j) 满足 dp_{i,k}>dp_{k+1,j}。二分查找可以做到 O(n^2\log n)，但是认真观察可以发现 f(i,j+1) \ge f(i,j)，并且判断是否成立是 O(1) 的，所以决策单调性优化到了 O(n^2)。

想到这里，接下来的部分就顺理成章了，分类讨论中转点 k 和 f(i,j) 的关系：

（1）k < f(i,j)，那么是一个形如 dp_{k,j}+a_k 的式子的值，这个和 i 无关，所以对于 j 维护一个单调队列即可。这里可能浪费一倍空间，解决方法有两个，第一个是单调队列和 dp 用一个数组，另外一个是先枚举 j，再倒序枚举 i。（这样空间还能用 vector 优化到 \dfrac{1}{2}n^2 个数）

（2）k \ge f(i,j)，那么是形如 dp_{i,k}+a_k 的东西，显然这个关于 k 单调递增，直接输出 k=f(i,j) 时的答案即可。

代码不长，即使手写单调队列优化常数都只有 30 行。

值得一提的是，如果令 f(i,j) 为区间 [i,j] 的决策点，这个在 i 固定的时候并没有决策单调性。最简单的反例是

n=7,a_i=i

并且，dp 的转移式不是单峰的，三分也不能解决。不知道有没有带一个 \log 的做法。（不容易直接优化到 n^2 的）