今天是 bct Day2，赛时 \(40+60+10+0=110\)，rk 70。
挂分原因是被 vector 卡常了/fn。然后 T4 捆绑 Sbt#1 T 了一个于是又没了 20pts。
评价是 ok 场，练习了对拍的使用。
发现 hm2ns 总是会随口否掉一些他看起来很错实际上对完了的性质，今天的 T2 是第三次出现这种情况，上一次是 CSPS T2，上上次忘了。
T1
算贡献即可，不需要用 vector 存质因数。
code
Show me the code
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef __int128 i128;
typedef unsigned long long u64;
const int N=1e6+88;
i64 a[N],b[N];
i64 ta[N],tb[N];
vector<pair<int,int> > k[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];ta[a[i]]++;}for(int i=1;i<=n;i++){cin>>b[i];tb[b[i]]++;}for(int i=1;i<=n;i++){for(int j=1;i*j<=n&&j<=i;j++){k[i*j].push_back(make_pair(i,j));}}i64 ans=0;for(int i=1;i<=n;i++){for(pair<int,int> as:k[i]){if(as.first==as.second){ans+=ta[as.first]*tb[as.second]*a[i];}else{ans+=ta[as.first]*tb[as.second]*a[i];ans+=tb[as.first]*ta[as.second]*a[i];}}}cout<<ans;return 0;
}T2
平衡树题，实际上是线段树题。
hm2ns 很快的否掉了对值域区间操作相对大小不变这个性质。但实际上这是对的。
然后在排完序的数组里做区间操作就是对值域操作，在段里记录对应值的左右端点。
需要不少标记。感谢 sheep 的对拍。
code
Show me the code
#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){i64 x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=5e5+5;
int n,q;
int a[N];
struct seg{int l;int r;int vl;int vr;int p1;int p0;bool rst;bool rid;int cnt;int cglg;
}t[N<<2];
int maxbp;
void b(int p,int l,int r){t[p].l=l;t[p].r=r;t[p].p1=t[p].p0=t[p].rst=t[p].rid=0;t[p].cglg=-1;maxbp=max(maxbp,p);if(l==r){t[p].vl=a[l];t[p].vr=a[r];t[p].p0=(a[l]%2==0)?1:0;t[p].p1=(a[l]%2==1)?1:0;return ;}int mid=l+r>>1;b(ls,l,mid);b(rs,mid+1,r);t[p].vl=t[ls].vl;t[p].vr=t[rs].vr;t[p].p1=t[ls].p1+t[rs].p1;t[p].p0=t[ls].p0+t[rs].p0;return ;
}
void pushdown(int p){if(!t[p].rst)return ;t[ls].rst=t[p].rst;t[rs].rst=t[p].rst;t[ls].rid=t[p].rid;t[rs].rid=t[p].rid;if(t[p].cglg!=-1){if(t[ls].vl%2==t[p].cglg)t[ls].vl--;if(t[ls].vr%2==t[p].cglg)t[ls].vr--;if(t[rs].vl%2==t[p].cglg)t[rs].vl--;if(t[rs].vr%2==t[p].cglg)t[rs].vr--;t[ls].cglg=t[p].cglg;t[rs].cglg=t[p].cglg;t[p].cglg=-1;}t[ls].vl-=t[p].cnt;t[ls].vr-=t[p].cnt;t[rs].vl-=t[p].cnt;t[rs].vr-=t[p].cnt; t[ls].cnt+=t[p].cnt;t[rs].cnt+=t[p].cnt;if(t[ls].rid==1){t[ls].p1=t[ls].p1+t[ls].p0;t[ls].p0=0;}else{t[ls].p0=t[ls].p1+t[ls].p0;t[ls].p1=0;}if(t[rs].rid==1){t[rs].p1=t[rs].p1+t[rs].p0;t[rs].p0=0;}else{t[rs].p0=t[rs].p1+t[rs].p0;t[rs].p1=0;}t[p].cnt=0;t[p].rst=0;t[p].rid=0;return ;
}
int modi(int p,int l,int r,int c){if(t[p].r>n||p==0||p>maxbp)return 0;if(l<=t[p].vl&&t[p].vr<=r){if(t[p].rst==1){if(t[p].rid==c){t[p].rid^=1;t[p].vl--;t[p].vr--;swap(t[p].p0,t[p].p1);t[p].cnt++;return t[p].r-t[p].l+1;}else{return 0;}}if(c==0){int pt=t[p].p0;t[p].p1+=t[p].p0;t[p].p0=0;t[p].rst=1;t[p].rid=1;if(t[p].vl%2==0)t[p].vl--;if(t[p].vr%2==0)t[p].vr--;t[p].cglg=c;
// t[p].cnt++;return pt;}if(c==1){int pt=t[p].p1;t[p].p0+=t[p].p1;t[p].p1=0;t[p].rst=1;t[p].rid=0;if(t[p].vl%2==1)t[p].vl--;if(t[p].vr%2==1)t[p].vr--;t[p].cglg=c;
// t[p].cnt++;return pt;}}pushdown(p);i64 sub=0;if(l<=t[ls].vr)sub+=modi(ls,l,r,c);if(t[rs].vl<=r)sub+=modi(rs,l,r,c);if(t[p].l!=t[p].r){t[p].vl=t[ls].vl;t[p].vr=t[rs].vr;t[p].p1=t[ls].p1+t[rs].p1; t[p].p0=t[ls].p0+t[rs].p0;}return sub;
}
int main(){cin>>n>>q;i64 ans=0;for(int i=1;i<=n;i++){a[i]=rd;ans+=a[i];}sort(a+1,a+1+n);b(1,1,n);for(int i=1;i<=q;i++){int l,r,c;cin>>l>>r>>c;ans-=modi(1,l,r,c);cout<<ans<<'\n';}return 0;
}赛时写了个简单易用的 check 程序，这是好的：
Show me the code
#define rd read()
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}int main(){string s;cin>>s;if(s=="1"){system("a.exe < a.in > a.out");}else if(s=="bk"){double beg=clock();system("a.exe < a.in > a.out");double ed=clock();system("brute.exe < a.in > a.ans");system("fc a.out a.ans");cout<<"program used "<<ed-beg<<' '<<" ms";}else if(s=="mul"){int k;cin>>k;while(k--){system("gen.exe > a.in");double beg=clock();system("a.exe < a.in > a.out");double ed=clock();system("brute.exe < a.in > a.ans");if(system("fc a.out a.ans")){cout<<"wa"<<'\n';Sleep(19923134);}cout<<"program used "<<ed-beg<<' '<<" ms";}}return 0;
}