CF742(Div.2)
https://codeforces.com/problemset/problem/1567/A ，签到
https://codeforces.com/problemset/problem/1567/B ，首先答案至少是a，也就是至少要有\(0,1,\dots,a-1\)这些异或和，记为\(S\)，这种时候一般只要再异或上一个\(S\oplus b\)就行了，\(S\)如果是\(b\)的话还不用异或，以及万一\(S\oplus b\)刚好是\(a\)，就会导致mex出问题，这种时候异或两个就行。
https://codeforces.com/problemset/problem/1567/C ，这题好难啊——，注意到进位全部往高位移一位之后，第0位进位给第2位，第1位给第3位，第2位给第4位，嗯就是奇数位单独进位，偶数位单独进位，所以把数字的位置按奇偶拆开成\(a,b\)，最后答案就是\((a+1)(b+1)-2\)，2是两个都是0的情况。
https://codeforces.com/problemset/problem/1567/D ，算个构造题（？），就是说\(n\)个十进制数之和为\(s\)，把他们看成11进制数做加法，使得11进制下的和最大。
首先答案肯定不会超过把\(n\)看成11进制的值，10进制看成11进制麻烦就在于一些原来能进位的地方进不了了，于是为了尽可能避免这个问题，拆数的时候就尽量把\(s\)拆成10的幂次！比如\(123=100+23=100+20+3\)这样，接着如果不够\(n\)个就从低往高的拆，暴力\(O(n^2\log n)\)就能过。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define endl ‘\n‘
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef vector<int> vi;
const int N=105;
int T,n,s,cnt;
int a[N],pw10[N];
void solve()
{
sort(a+1,a+cnt+1);
rep(i,1,cnt)rep(j,0,9)if(pw10[j]<a[i]&&a[i]<pw10[j+1])
{
a[++cnt]=pw10[j];
a[i]=a[i]-pw10[j];
return;
}
rep(i,1,cnt)rep(j,1,9)if(a[i]==pw10[j])
{
a[++cnt]=pw10[j-1];
a[i]=a[i]-pw10[j-1];
return;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
pw10[0]=1;
rep(i,1,9)pw10[i]=pw10[i-1]*10;
cin>>T;
rep(tc,1,T)
{
cin>>s>>n;
cnt=1;a[cnt]=s;
while(cnt<n)solve();
sort(a+1,a+n+1);
rep(i,1,n)cout<<a[i]<<‘ ‘;cout<<endl;
}
return 0;
}
https://codeforces.com/problemset/problem/1567/E ，线段树，我维护的方法比较暴力，每个节点存上答案、区间长度、左右端点的值，以及最长non-decreasing的prefix和suffix长度。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define endl ‘\n‘
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef vector<int> vi;
const int N=2e5+5;
struct nod
{
ll s;
int len,vl,vr,len_l,len_r;
}tr[N<<2];
int n,q;
int a[N];
#define lson (node<<1)
#define rson (node<<1|1)
ll calc(ll x){return 1ll*x*(x+1)/2;}
nod merge(nod ls,nod rs)
{
nod ret;
ret.vl=ls.vl;ret.len_l=ls.len_l;
ret.vr=rs.vr;ret.len_r=rs.len_r;
ret.len=ls.len+rs.len;
if(ls.vr>rs.vl)ret.s=ls.s+rs.s;
else
{
ret.s=ls.s+rs.s-calc(ls.len_r)-calc(rs.len_l)
+calc(ls.len_r+rs.len_l);
if(ls.len==ls.len_l)
ret.len_l=ls.len_l+rs.len_l;
if(rs.len==rs.len_r)
ret.len_r=rs.len_r+ls.len_r;
}
return ret;
}
void push_up(int node)
{
tr[node]=merge(tr[lson],tr[rson]);
}
void build(int node,int l,int r)
{
if(l==r)
{
tr[node].s=tr[node].len=tr[node].len_l=tr[node].len_r=1;
tr[node].vl=tr[node].vr=a[l];
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
push_up(node);
}
nod query(int node,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return tr[node];
int mid=(l+r)>>1;
nod ls,rs;
ls.len=rs.len=-1;
if(mid>=ql)ls=query(lson,l,mid,ql,qr);
if(mid+1<=qr)rs=query(rson,mid+1,r,ql,qr);
if(ls.len==-1)return rs;
else if(rs.len==-1)return ls;
else return merge(ls,rs);
}
void modify(int node,int l,int r,int x,int y)
{
if(l==r)//Here!Not l==x hhh
{
tr[node].vl=tr[node].vr=y;
return;
}
int mid=(l+r)>>1;
if(mid>=x)modify(lson,l,mid,x,y);
else modify(rson,mid+1,r,x,y);
push_up(node);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
rep(i,1,n)cin>>a[i];
build(1,1,n);
rep(i,1,q)
{
int op,x,y;
cin>>op>>x>>y;
if(op==1)modify(1,1,n,x,y);
else cout<<query(1,1,n,x,y).s<<endl;
}
return 0;
}