寒假训练营2
C 字典树
求升序子序列个数，其中最大值和最小值的异或小于等于d。如果确定了最小值最大值分别为a[i]，a[j]，，那么中间的数都可选可不选，这组maxmin对总方案数的贡献就是2^(j-i-1)。
直接二重循环枚举minmax显然是不行的，只能枚举一个，然后logn查询另一个。但这个查询是要查询抑或上一个数不超过d的元素个数，此时用字典树才能达到logn。
字典树用叶子节点表示一个元素，从根节点到叶结点的路径则是这个元素的二进制表示，0为左，1为右。查询时，由于异或的结果不大于d，如果d某一位是1，那么minmax在这一位可以一样，也可以不一样，如果不一样，接着往下走，直到达到叶节点，更新叶节点代表的数的贡献；如果一样,异或后这一位为0，由于前面位都是d的子集，后面位可以任取了，都一定不大于d，那么就不用往下找了，直接加上这棵子树的贡献。
对于贡献，可以拆开成2^(j-1)/2^i，j是max决定的，查询时只用求sigma(1/2^i)，也就是说每个叶节点对答案的贡献是1/2^i，那么我们把1/2^i保存在字典树节点上，查询时累加。
涉及到除法的模运算，用逆元。
为了不漏，先对原数组元素排序，然后从小到大枚举max
ll val;
int son[2];
}t[N*32];
void init(void){
cnt=1;
for(int i=0;i<=n*32;i++){
t[i].val=t[i].son[1]=t[i].son[0]=0;
}
}
void insert(ll val,int x){
int u=1;
for(int i=30;i>=0;i--){
int s=(x>>i)&1;
if(t[u].son[s]==0)t[u].son[s]=++cnt;
u=t[u].son[s];
t[u].val=(t[u].val+val)%mod;
}
}
ll get(int x){
int u=1;
ll ret=0;
for(int i=30;i>=0;i--){
int s=(x>>i)&1;
int m=(k>>i)&1;
if(m){
if(t[u].son[s])ret=(ret+t[t[u].son[s]].val)%mod;
u=t[u].son[s^1];
}
else u=t[u].son[s];
}
ret=(ret+t[u].val)%mod;
return ret;
}
signed main(){
int T;
cin>>T;
while(T--){
cin>>n>>k;
init();
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
ll ans=1;
for(int i=2;i<=n;i++){
insert(inv(qpow(2,i-1)),a[i-1]);
ans=(ans+1+get(a[i])*qpow(2,i-1))%mod;
}
cout<<ans<<'\n';
}
}
D 同余最短路
初始在k位，目标是到n位，有m张卡牌可以让位置上升a[i]，代价为b[i]，可以重复使用，位置大于n时会取模，问到达n的最小代价是多少？
可以看成一个最短路问题。每个位置都有m条出边，终点为从这点出发，用了第i张牌后的位置，边权为这张牌的代价，然后以k为起点，n为终点跑一个最短路就好了，最短路程就是最小代价。
需要注意的是不用建图，找出边时遍历m种卡牌，算出对应终点就行。
{
int to,val,next;
}edge[1000*N];//存边数组初始化为边数大小m
struct node
{
int val,no;
};
bool operator<(node a,node b)
{
return a.val>b.val;//重载运算符
}
priority_queue<node>q;
int n,m,s,a[N],b[N],d[N],cnt,head[N],vis[N];
void add(int u,int v,int w){
edge[++cnt]=(EDGE){v,w,head[u]};
head[u]=cnt;
}
signed main(){
int T;
cin>>T;
while(T--){
cin>>n>>m>>s;
s--;
rep(i,0,n-1)d[i]=1e18;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
while(q.size())q.pop();
cnt=0;
rep(i,1,m){
cin>>a[i]>>b[i];
}
// rep(i,1,n){
// rep(j,1,m){
// add(i,(i+a[j])%n,b[j]);
// }
// }
d[s]=0;
q.push(node{0,s});
while(!q.empty())
{
int x=q.top().no;//取堆顶编号
q.pop();
if(vis[x])continue;//在a中直接删掉
vis[x]=1;//标记为在a中
rep(i,1,m)//遍历m条出边
{
int to=(x+a[i])%n;
if(d[to]>d[x]+b[i])
{
d[to]=d[x]+b[i];
if(!vis[to])
q.push(node{d[to],to});
}
}
}
if(d[n-1]!=1e18)cout<<d[n-1]<<'\n';
else cout<<-1<<'\n';
}
}
F 思维
每次从各个颜色最右边的宝石宝石中选择一个，消除该位置及其右边所有宝石，问最少需要多少次可以消除所有宝石？
第一问用了个复杂的贪心，只能过第一问。保存每个颜色的宝石的最右边的位置，然后每次取最小值，删除右边，然后更新所有颜色宝石的最右边的位置。这个更新要用Lowerbound，然后最多有n种宝石，每轮更新的复杂度就要到nlogn了。可能更新轮数不会太多，最终复杂度也还能过，但是实现起来太麻烦了，不写了。
一种更简单也更快的贪心是，从后往前遍历，如果所有颜色的宝石都出现过一次了，就把当前位置及右边的宝石都删掉，一位内所有颜色的宝石都出现过了，说明所有颜色的最右侧都已经出现了，而最后出现的，就是所有颜色最右侧点中最靠左的点，从这点开始删除可以删掉最多的宝石，也就可以使删除次数最少。
实现时需要注意的是，需要记录每种颜色的个数，如果某种颜色已经全删掉了，那么就应该把颜色总数减一。
map<int,int>cnt;
map<int,int>vis;
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
cnt.clear();
vis.clear();
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;//统计每种颜色个数
}
int vised=0;//出现的颜色数
int ans=0;
int tot=cnt.size();//颜色总数
int up=n;//上次删除点，删除的上界
for(int i=n;i>=1;i--){
if(!vis[a[i]]){//记录每种颜色是否出现
vis[a[i]]=1;
vised++;
}
if(vised==tot){//如果都出现了
vised=0;//重置
ans++;
vis.clear();
for(int j=i;j<=up;j++){
cnt[a[j]]--;//更新每种颜色个数
if(!cnt[a[j]])tot--;//如果有颜色删光了，更新总颜色
}
up=i-1;//更新上界
}
}
cout<<ans<<'\n';
}
}
G线段树/树状数组
对每个查询l,r，找到[l,r]内一个区间[i,j]，确定一个x，使得sum[i,x]-sum[x,j]最大。由于所有元素都是非负的，那么首先，i一定等于l，因为如果不等于l,sum[l,x]-sum[x,j]一定比sum[i,x]-sum[x,j]更大，[i,j]和x就不是最大的选法了。其次，对于一个[i,j],x一定等于j，还是因为所有数都是非负的，减数肯定越少越好，被减数肯定越多越好。
那么对于一个查询l,r，我们实际上就是要维护max(sum[l,i] - a[i+1] * 2)，其中i<r。
如果使用树状数组，我们可以logn查询sum[l,i]，但是求max(sum[l,i] - a[i+1] * 2)还是要遍历[l,r]的，n次查询，lr范围也在1到n，总复杂度为n^2logn，显然是不行的。
这里可以用一个巧妙的贪心，就是每次查询都不用遍历[l,r]，只要遍历从r-1往前最多32个位置就可以了。因为对于每次计算的f[i]=sum[l,i] - a[i+1] * 2，i往前挪一位时，f[i-1]=f[i]+a[i] - 2 * a[i-1]，只有a[i] - 2 * a[i-1]>0,也就是a[i-1]<a[i]/2时，f[i-1]才会大于f[i]。而元素范围不超过Int(2^31)的话，一个满足a[i-1]<a[i]/2的连续序列最长为32，因此从r-1开始往前遍历，f[i]最多在前32次能变大，那么为了求最大值，我们就只用遍历前面最多32个位置。
这样做复杂度就降低到了32nlogn，是可以接受的。
return x&(-x);
}
void add(int x,int v){
while(x<=n){
b[x]+=v;
x+=lowbit(x);
}
}
ll s(int x){
ll ret=0;
while(x>0){
ret+=b[x];
x-=lowbit(x);
}
return ret;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>q;
for(int i=1;i<=n;i++)b[i]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);//建树
}
for(int i=1;i<=q;i++){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
add(x,y-a[x]);//单点修改
a[x]=y;
}
else{
ll ans=-1e18;
for(int j=y;j>=max(x+1,y-32);j--){//往前最多32个
ans=max(ans,s(j)-s(x-1)-2*a[j]);
}
cout<<ans<<'\n';
}
}
}
}
树状数组只能用这种贪心才能通过，是因为树状数组只支持修改和查询区间和这两种操作，而线段树更加灵活，可以维护区间上更多的量，因此不需要用这种贪心也可以通过。前面是说了，我们需要的就是max(sum[l,i] - a[i+1] * 2)，那么我们就可以在线段数上维护这个量。两个区间合并时，新的max可能是左区间的max，右区间的max，或者是左区间全部加上右区间max。
sum是一个前缀和，但是中途可能有修改，因此也需要一个支持log查询修改区间和的结构来做，这里为了方便用一个树状数组。
修改时要对树状数组进行单点修改，也要修改原始数组a（更新线段树时要用到a），还要对线段树进行修改。由于线段树维护的是max(sum[l,i] - a[i+1] * 2)，其中sum是前缀和，对原数组进行单点修改会影响后面每一个sum的值，也就会影响后面所有max(sum[l,i] - a[i+1] * 2)，修改后需要给线段树上修改位置直到结尾所有点都加上修改值。
ll a[N],b[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
while(x<=n){
b[x]+=v;
x+=lowbit(x);
}
}
ll s(int x){
ll ret=0;
while(x){
ret+=b[x];
x-=lowbit(x);
}
return ret;
}
struct Tree{
struct Node{
int l,r;
ll mx,add;
}tr[N<<2];
void pushup(int u){
tr[u].mx=max(tr[ls].mx,tr[rs].mx);
}
void pushdown(int u){
if(tr[u].add){
tr[ls].mx+=tr[u].add;//下放，最大值加
tr[rs].mx+=tr[u].add;
tr[ls].add+=tr[u].add;//标记加
tr[rs].add+=tr[u].add;
tr[u].add=0;
}
}
void build(int u,int l,int r){
tr[u]={l,r,0,0};
if(l==r){
tr[u].mx=s(l-1)-a[l];//初始化成要维护的值
return;
}
int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int val){
if(tr[u].l>=l&&tr[u].r<=r){ //区间修改
tr[u].mx+=val;//单点加v,后面sum都加v，因此区间mx加v
tr[u].add+=val;//区间也加v，需要lazytag
return ;
}
else{
int mid=(tr[u].l+tr[u].r)>>1;
pushdown(u);
if(mid>=l) modify(ls,l,r,val);
if(r>mid) modify(rs,l,r,val);
pushup(u);
}
}
ll query(int u,int l,int r){
if(r<tr[u].l||tr[u].r<l) return -1e18;//维护最大值，默认-inf
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mx;
pushdown(u);
return max(query(ls,l,r),query(rs,l, r));
}
}t;
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>q;
for(int i=1;i<=n;i++)b[i]=0;//树状数组清零
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);//加入前缀和树状数组
}
t.build(1, 1, n);//线段树建树就包含清空了
for(int i=1;i<=q;i++){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
t.modify(1, x, x, a[x]-y);
//输入是修改为，板子是加
//x位置维护的是sum[l-1]-a[l]，而加是加在a[l]上的
//因此加y-a[x]对x点值的贡献是负的
if(x<n)t.modify(1, x+1, n, y-a[x]);
//对后面的点来说是加在sum[l-1]上的，
//因此贡献是正的
add(x,y-a[x]);//更新前缀和
a[x]=y;//最后再更新原数组，因为上面的增量都要用上一次a[x]算
}
else{
cout<<t.query(1, x+1, y)-s(x-1)<<'\n';
//两个人最少都要有一段因此长度最短为2，[i,j]最小为[l,l+1]
//前缀和需要减去左端点s(l-1)
}
}
}
}
京公网安备 11010502036488号