玄关求助

ST表的query函数中

我把

int k = log2(r-l+1);

换成

int k = log2(r-l+1);

k=___lg(r-l+1)

就会从TLE变成AC

为了验证两个式子是否相等,我

assert((int)log2(r-l+1)==__lg(r-l+1)) ren

却仍然可以AC

代码如下

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
const int N=5E5+5;
struct node
{
	int x, y;
}st[N][20];
node operator +(const node &a,const node &b)
{
	node ret;
	ret.x=__gcd(a.x,b.x);
	ret.y=a.y|b.y;
	return ret;
}
bool operator ==(const node &a,const node &b)
{
	return a.x==b.x&&a.y==b.y;
}
node query(int l,int r)
{
	int k=log2(r-l+1);
	k=__lg(r-l+1);
	return st[l][k]+st[r-(1<<k)+1][k];
}
bool get(node a,int k)
{
	return (a.x^a.y)==k;
}
void solve()
{
	 int n,K;
	 cin>>n>>K;
	 vector<int>a(n+1);
	 for(int i=1;i<=n;i++)
	 {
	 	cin>>a[i];
	 	st[i][0]={a[i],a[i]};
	 }
	 for(int k=1;(1<<k)<=n;k++)
	 {
	 	for(int i=1;i+(1<<k)-1<=n;i++)
	 	{
	 		st[i][k]=st[i][k-1]+st[i+(1<<k-1)][k-1];	
	 		//cerr<<i<<" "<<k<<" "<<st[i][k].x<<"\n";
	 	}
	 }
	 ll ans=0;
	 for(int i=1;i<=n;i++)
	 {
	 	int now=i;
	 	while(now<=n)
	 	{
	 		int l=now,r=n;
	 		node cur=query(i,now);
	 		while(l<r)
	 		{
	 			int mid=(l+r+1)/2;
	 			if(query(i,mid)==cur)
	 			{
	 				l=mid;
	 			}
	 			else
	 			{
	 				r=mid-1;
	 			}
	 		}
	 		if(get(cur,K))
	 		{
	 			ans+=l-now+1;
	 		}
	 		now=l+1;	
	 	}
	 }
	 cout<<ans;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
}