CF1718A
题意：
给定一个序列，每次可以花费\(\lceil\frac{r-l+1}{2}\rceil\)的代价选择一段区间\([l,r]\)，并把区间里的每个数字异或上\(x\)，最少花费多少代价可以让整个序列变成\(0\)？
\(1\leq n\leq 10^5,0\leq a_i<2^{30}\)
题解：
区间异或可以想到前缀异或和。
而且这个上取整性质说明区间长度是\(2\)的倍数会很赚，而且可以每次只选长度为\(1\)和\(2\)的区间，更大的区间可以由此拼来。
那么假如有\(a,b,c,d\)序列，最坏情况下要\(4\)秒完成。
那么怎么才能优化到\(3\)秒呢，当然是每次选长度为\(2\)的区间。
假如第一次异或完是\(0,a\oplus b,c,d\)
第二次\(0,0,a\oplus b\oplus c,d\)
第三次\(0,0,0,a\oplus b\oplus c\oplus d\)
如果三次可以完成，那么必然有\(a\oplus b\oplus c\oplus d=0\)
也就是这一段的异或和为\(0\)。
所以如果存在某一段异或和为零，这一段就可以少异或一次。
可以根据这个性质做一个动态规划。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n;
cin>>n;
vector<int> a(n+2),b(n+2);
for(int i=1;i<=n;++i)
{
cin>>a[i];
b[i]=b[i-1]^a[i];
}
map<int,int> q;
vector<int> dp(n+1);
q[0]=0;
dp[0]=0;
for(int i=1;i<=n;++i)
{
dp[i]=dp[i-1];
if(q.find(b[i])!=q.end())
{
dp[i]=max(dp[i],dp[q[b[i]]]+1);
}
q[b[i]]=i;
}
cout<<n-dp[n]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
CF1718C
题意：
给定一个长度为\(n\)的循环序列，请你给出两个数字\(1\leq s\leq n,1\leq k<n\)，满足从\(s\)开始，每次向后走\(k\)步，执行\(n\)次，走过的位置权值之和最大，求最大的权值和。
有\(m\)次修改操作，每次修改一个位置上的数字。
\(1\leq n,m\leq 2*10^5\)
题解：
其实可以发现本质不同的走法都是\(n\)的不同因子，这样就只有\(n\sqrt{n}\)种不同的序列了，但是要维护这些的最大值还要多个\(log\)，很难通过。
其实可以不用，因为发现对每种质因子只要提取最大的一个因子出来而不用其他的因子，换句话说，有用的因子们，不存在一个是另一个的因子。
因为\(k\)越大，循环周期越短，就可以更高效率的走更大的数字。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<int> a(n+1);
vector<vector<int> > ans(n+1);
vector<int> d;
int nn=n;
for(int i=2;i<=nn;++i)
{
if(nn%i==0)
{
d.emplace_back(n/i);
ans[n/i].resize(n/i);
while(nn%i==0) nn/=i;
}
}
sort(d.begin(),d.end());
for(int i=0;i<n;++i)
{
cin>>a[i];
}
int s=d.size();
multiset<int> q;
for(int i=0;i<s;++i)
{
int len=d[i];
for(int st=0;st<len;++st)
{
int pos=st,sum=0;
while(pos<n)
{
sum+=a[pos];
pos+=len;
}
ans[len][st]=sum*len;
q.insert(ans[len][st]);
}
}
cout<<*(q.rbegin())<<'\n';
for(int tt=1;tt<=m;++tt)
{
int x,y;cin>>x>>y;
--x;
for(int i=0;i<s;++i)
{
int len=d[i];
int st=x%len;
q.erase(q.find(ans[len][st]));
ans[len][st]-=a[x]*len;
ans[len][st]+=y*len;
q.insert(ans[len][st]);
}
a[x]=y;
cout<<*(q.rbegin())<<'\n';
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
CF1712E
题意：
给定\(m\)个\(l,r\)，求满足\(l\leq i<j<k\leq r\)且\(lcm(i,j,k)\geq i+j+k\)的数对的数量。
\(m\leq 2*10^5,1\leq l+2\leq r\leq 2*10^5\)
题解：
正难则反，首先所有数对的数量是\(\dbinom{r-l+1}{3}\)
然后减去不满足要求的，直觉发现\(lcm\)比\(i+j+k\)要大许多，不满足的数量不会太多。
不妨考虑\(lcm\)是多少，首先他们一定是\(k\)的倍数。
其次，\(i+j+k<k+k+k=3k\)，所以可能的结果只有\(lcm=k\)或\(lcm=2k\)
当\(lcm=k\)时，一定满足\(i+j+k>lcm=k\)，所以只要统计对每个\(k\)来说，有多少符合要求的\(i|k,j|k\)
当\(lcm=2*k\)时，要满足\(i+j+k>lcm=2k\)，就要\(i+j>k\)
而且\(i\)和\(j\)至少有一个要比\(k\)多乘一个\(2\)。
不妨设\(i=a*k,j=b*k\)，那么有\(a+b>1\)
而且至少有一个分子是\(2\)的倍数。
打个表可以发现，可行的情况只有
\(i=3*a,j=4*a,k=6*a,lcm=12*a\)
或者
\(i=5*a,j=6*a,k=15*a,lcm=30*a\)
接下来就是\(HH\)的项链，考验树状数组功底了。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n=200000,m;
cin>>m;
vector<int> ans(m+1);
struct node
{
int l,r,id;
bool operator < (const node &t) const
{
return r<t.r;
}
};
vector<node> a(m+1);
for(int i=1;i<=m;++i)
{
cin>>a[i].l>>a[i].r;
a[i].id=i;
}
sort(a.begin()+1,a.end());
vector<vector<int> > d(n+1);
vector<int> tr(n+1);
auto update=[&](int x,int k) -> void
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;
};
auto query=[&](int x) -> int
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
return sum;
};
for(int i=n;i>=1;--i)
{
for(int j=i+i;j<=n;j+=i)
{
d[j].emplace_back(i);
}
}
int t=1;
for(int i=1;i<=n;++i)
{
int cnt=0;
for(int j:d[i])
{
update(j,cnt);
++cnt;
}
if((i*2)%12==0) update((i*2)/4,1);
if((i*2)%30==0) update((i*2)/5,1);
while(t<=m&&a[t].r<=i)
{
int len=a[t].r-a[t].l+1;
ans[a[t].id]=len*(len-1)*(len-2)/6-(query(i)-query(a[t].l-1));
++t;
}
}
for(int i=1;i<=m;++i) cout<<ans[i]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/