T1
statement
给定 \(l,r\)，选出一些 \(\in [l,r]\) 的数，问他们的按位或有多少种不同的值。
solution
沙比分讨题。
考虑求出 \(l,r\) 最高的不同位 \(i\)，比这位更高的就不影响了，考虑第 \(i\) 位选或不选。
-
不选，那么我们可以用的数就是 \(l\to 2^i-1\)，显然不同数就是 \(2^i-l\) 。
-
选 在包含第 \(i\) 位的情况下，可选的数除了上边的 \(l\to 2^i-1\)，有一些低位可以用，求出个数 \(c\) ，那么这一部分就是 \(2^i-l+2^c-max(0,l-2^c)\) ，记得把公共部分剪掉。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL l,r;
LL get(LL x,LL i){return (x>>i)&1ll;}
LL gen(LL c,LL i){return c<<i;}
int main()
{
cin>>l>>r;
LL i=60;
for(i=60;i>=0;i--)
if(get(l,i)!=get(r,i))break;
else l-=gen(get(l,i),i),r-=gen(get(r,i),i);
if(i<0)
{
cout<<1;
return 0;
}
LL x=0;
for(LL j=0;j<i;j++)x+=gen(get(r,j),j);
LL c=0;
for(LL j=0;j<i;j++)if(gen(1,j)<=x)c++;
LL v=gen(1,i)-1,w=gen(1,c)-1;
LL ans=v-l+1;
ans+=(v-l+1)+w+1-max(0ll,w-l+1);
cout<<ans;
return 0;
}
T2
statement
构造一个长度 \(n\)，值域 \(10^9\) 的序列，使得恰好有 \(k\) 个不同的区间和。
solution
逆天构造题。
考虑如果我们能使得所有后缀的和不同，那么我们就能从 \((n,k)\to (n-1,k-n)\) 。
我们不断执行上述过程直到 \(k\leq 2n-1\) ，此时我们可以给出一组构造：
-
若 \(1\leq k\leq n\)，我们构造一个前缀是 \(1\)，后缀是 \(0\) 的即可。
-
若 \(n<k<2n\) ，我们构造一个前缀是 \(2\)，后缀是 \(1\) 的即可。
设上述的和 \(=sum\) 。
我们接下来在数列后面加上一个 \(inf\)，然后依次是 \(inf+sum+1\)，\(inf+2sum+2\)，\(inf+3sum+3\)……
容易证明符合符合要求。
code
#include<bits/stdc++.h>
using namespace std;
int n,K;
int a[1020];
void solve()
{
scanf("%d %d",&n,&K);
int m=n;
while(K>2*m-1)
{
K-=m;
m--;
}
if(K<=m)
{
for(int i=1;i<=K-1;i++)a[i]=1;
for(int i=K;i<=m;i++)a[i]=0;
}
else
{
int B=K-m,A=m-B;
for(int i=1;i<=A;i++)a[i]=1;
for(int i=A+1;i<=m;i++)a[i]=2;
}
int inf = 1e8,sum=0;
for(int i=1;i<=m;i++)sum+=a[i];sum++;
a[++m]=inf;
while(m<n)inf+=sum,a[++m]=inf;
for(int i=1;i<=n;i++)printf("%d ",a[i]);
printf("\n");
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
T3
statement
坚果保龄球小游戏。
维护若干操作：
-
在某个格子 $(r,c) $ 加入一个血量为 \(h\) 的僵尸。
-
在格子 \((r,c)\) 释放一个坚果，坚果会向右撞，撞到僵尸后会沿着相反的对角线移动（也就是一个折线状），并且给出第一次撞击后是沿着主对角线还是副对角线移动，被撞到的僵尸血量会减一，你需要输出撞到的僵尸个数以及撞死的僵尸个数。
-
所有僵尸向左移动 \(t\) 步，横坐标小于 \(0\) 的会死掉，你需要输出死掉的僵尸个数，
solution
牛魔DS题。
撞的路线就是若干条链，可以用平衡树维护，撞的过程就是区间减以及查询区间min是否为0。
这样有一个问题是，每个僵尸会处于两个链中（左上和左下），必须两个链被撞的总次数达到 \(h\) 才会死。
一个经典的 \(trick\) 是减半警报器，我们把每个僵尸在两条链中的血量设为 \(h/2\)，那么如果该僵尸死了，必定有一条链达到 \(h/2\) 。当然到达 \(h/2\) 不一定会死，但是我们此时检查一下，如果不满足就更新一下现在的血量，那么每次一定除以二，所以复杂度 \(O(n\log n\log V)\) 。
细节多的一批。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
int n,m,q,cnt=0;
map<int,int> id[3];//行,左下右上对角线，左上右下对角线
int tot[3];
int getid(int c,int x)
{
if(id[c][x]) return id[c][x];
return id[c][x]=++tot[c];
}
char s[200];
struct Zombine
{
int x,y,h;
}P[N];
#define PII pair<int,int>
#define mk(x,y) make_pair(x,y)
#define X(x) x.first
#define Y(x) x.second
int rest[N][2];//0 代表从上往下，1代表从下往上
int namestk[N],top=0,idx=0;
int getid()
{
if(top)return namestk[top--];
return ++idx;
}
struct node
{
int xpos,val,tag,mn;
int ls,rs,key,fa,siz;
#define siz(x) tr[x].siz
#define fa(x) tr[x].fa
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define key(x) tr[x].key
#define xpos(x) tr[x].xpos
#define val(x) tr[x].val
#define tag(x) tr[x].tag
#define mn(x) tr[x].mn
}tr[N*2];
void pushup(int k)
{
mn(k)=val(k);
siz(k)=siz(ls(k))+siz(rs(k))+1;
if(ls(k))mn(k)=min(mn(k),mn(ls(k))),fa(ls(k))=k;
if(rs(k))mn(k)=min(mn(k),mn(rs(k))),fa(rs(k))=k;
}
void pushtag(int k,int v)
{
val(k)+=v;
tag(k)+=v;
mn(k)+=v;
}
void pushdown(int k)
{
if(tag(k))
{
pushtag(ls(k),tag(k));
pushtag(rs(k),tag(k));
tag(k)=0;
}
}
int Merge(int x,int y)
{
if(!x||!y)return x+y;
pushdown(x);pushdown(y);
if(key(x)<key(y))
{
fa(ls(x))=0;fa(rs(x))=0;
rs(x)=Merge(rs(x),y);
pushup(x);
return x;
}
fa(ls(y))=0;fa(rs(y))=0;
ls(y)=Merge(x,ls(y));
pushup(y);
return y;
}
void split(int k,int val,int &x,int &y)
{
fa(ls(k))=0;fa(rs(k))=0;
if(!k)
{
x=y=0;
return;
}
pushdown(k);
if(xpos(k)<=val)
{
x=k;
split(rs(k),val,rs(k),y);
}
else
{
y=k;
split(ls(k),val,x,ls(k));
}
pushup(k);
}
int findroot(int x)
{
while(fa(x))x=fa(x);
return x;
}
int tag[N];
set<PII> st[3][N],H;
int col[N][2];
int L=1;
bool del[N];
int pre(int c,int x,int v)
{
x=getid(c,x);
auto u=st[c][x].lower_bound(mk(v,0));
if(u==st[c][x].begin())return 0;
int o=(*--u).second;
if(del[o])return 0;
return o;
}
int nxt(int c,int x,int v)
{
x=getid(c,x);
auto u=st[c][x].lower_bound(mk(v,0));++u;
if(u==st[c][x].end())return 0;
int o=(*u).second;
if(del[o])return 0;
return o;
}
int gen(int x,int c){return x*2+c-1;}
int u1=0,u2=0;
void maintain(int i)
{
int x=P[i].x,y=P[i].y;
int l1=pre(1,x-y,x),l2=pre(2,x+y,x);
int r1=nxt(1,x-y,x),r2=nxt(2,x+y,x);
if(l1&&r1)
{
int p=findroot(gen(l1,0));
split(p,x,u1,u2);
}
if(l2&&r2)
{
int p=findroot(gen(l2,1));
split(p,x,u1,u2);
}
int lim=(P[i].h+1)/2;
int t=gen(i,1);
key(t)=rand();fa(t)=ls(t)=rs(t)=tag(t)=0;siz(t)=1;
xpos(t)=x;val(t)=mn(t)=lim;
if(l1)t=Merge(findroot(gen(l1,0)),t);
if(r2)t=Merge(t,findroot(gen(r2,0)));
t=gen(i,0);
key(t)=rand();fa(t)=ls(t)=rs(t)=tag(t)=0;siz(t)=1;
xpos(t)=x;val(t)=mn(t)=lim;
if(l2)t=Merge(findroot(gen(l2,1)),t);
if(r1)t=Merge(t,findroot(gen(r1,1)));
}
void Dele(int i)
{
int x=gen(i,0),y=gen(i,1);
int p=findroot(x),q=findroot(y);
split(p,P[i].x,p,u2);
split(p,P[i].x-1,u1,p);
p=Merge(u1,u2);
split(q,P[i].x,q,u2);
split(q,P[i].x-1,u1,q);
q=Merge(u1,u2);
}
void Mark(int i)
{
int x=P[i].x,y=P[i].y;
int l1=pre(1,x-y,x),l2=pre(2,x+y,x);
int r1=nxt(1,x-y,x),r2=nxt(2,x+y,x);
int p=findroot(gen(i,0)),q=findroot(gen(i,1));
split(p,P[i].x,p,u2);
split(p,P[i].x-1,u1,p);
split(q,P[i].x,q,u2);
split(q,P[i].x-1,u1,q);
if(l1&&r1) Merge(findroot(gen(l1,0)),findroot(gen(r1,1)));
if(l2&&r2) Merge(findroot(gen(l2,1)),findroot(gen(r2,0)));
del[i]=1;
st[0][getid(0,y)].erase(mk(x,i));
st[1][getid(1,x-y)].erase(mk(x,i));
st[2][getid(2,x+y)].erase(mk(x,i));
}
int seq[N],sc=0;
void dfs(int T)
{
if(!T)return;
pushdown(T);
if(mn(T)>0)return;
dfs(ls(T));
if(val(T)==0) seq[++sc]=T;
dfs(rs(T));
pushup(T);
}
int stk[N],tmp=0;
inline int getv(int x)
{
int r=x,h=0;
while(fa(r))r=fa(r),h+=tag(r);
return val(x)+h;
}
int pv[N][2];
void Hit(int S,int T)
{
pushtag(T,-1);
sc=0;
dfs(T);
int res=0;
for(int j=1;j<=sc;j++)
{
int i=(seq[j]+1)/2;
pv[i][0]=getv(gen(i,0));
pv[i][1]=getv(gen(i,1));
}
int ans1=siz(T);
Merge(S,T);
for(int j=1;j<=sc;j++)
{
int i=(seq[j]+1)/2;
int lv=pv[i][0],rv=pv[i][1];
int lim=(P[i].h+1)/2;
int w=(lim-lv)+(lim-rv);
P[i].h-=w;
if(P[i].h)
{
lim=(P[i].h+1)/2;
int x=gen(i,0),y=gen(i,1);
int p=findroot(x),q=findroot(y);
split(p,P[i].x,p,u2);
split(p,P[i].x-1,u1,p);
val(p)=mn(p)=lim;
p=Merge(Merge(u1,p),u2);
split(q,P[i].x,q,u2);
split(q,P[i].x-1,u1,q);
val(q)=mn(q)=lim;
q=Merge(Merge(u1,q),u2);
}
else
{
Mark(i),res++;
}
}
printf("%d %d\n",ans1,res);
}
int main()
{
// freopen("a.in","r",stdin);
//freopen("a.ans","w",stdout);
cin>>n>>m>>q;
while(q--)
{
scanf("%s",s+1);
if(s[1]=='a')
{
int y,x,h;
scanf("%d %d %d",&y,&x,&h);
x=x+L-1;
int i=++cnt;
P[cnt]=(Zombine){x,y,h};
st[0][getid(0,y)].insert(mk(x,cnt));
st[1][getid(1,x-y)].insert(mk(x,cnt));
st[2][getid(2,x+y)].insert(mk(x,cnt));
H.insert(mk(x,i));
maintain(i);
}
else if(s[1]=='t')
{
int t;
scanf("%d",&t);
int res=0;
while(!H.empty())
{
auto u=H.begin();
if(del[(*u).second])
{
H.erase(u);
continue;
}
if((*u).first>L+t-1) break;
res++;
Mark((*u).second);
H.erase(u);
}
printf("%d\n",res);
L+=t;
}
else
{
int x,y,d;
scanf("%d %d %d",&y,&x,&d);
x=x+L-1;
if(id[0].find(y)==id[0].end())
{
printf("0 0\n");
continue;
}
auto u=st[0][getid(0,y)].lower_bound(mk(x,0));
if(u==st[0][getid(0,y)].end())
{
printf("0 0\n");
continue;
}
int i=(*u).second;
if(d==-1)d=1;
else d=0;
int p=findroot(gen(i,d));
split(p,P[i].x-1,u1,u2);
Hit(u1,u2);
}
}
return 0;
}