A.异或运算
题意：给出$a[n]$,$b[m]$.一个二维数组$c[i][j]=a[i]\otimes b[j]$。给出$p$个询问。每次询问某个矩形区域内的第$k$大值。
$ n<=1000$ $m<=300000$ $p<=500$
题解：矩形第k大很容易让人想到矩阵乘法这道题，但这是行不通的。因为无法建出整个二维数组，而且询问本身也并不多。
考虑题目的特殊性，这个二维数组是由一个异或确定的。
异或之类的问题从最高位逐位确定的方法一定是对的。
不妨假设当前考虑到第$i$位,那么我们需要知道
满足$x∈[xl,xr]$，$y∈[yl,yr]$，且$（a[x]\otimes b[y]\otimes ans）>>i==1$的二元组$（x，y）$的数量。
感觉$O（1）$是不能做的。然而$n$为什么比起$m$这么小呢？很显然就是让我们暴力呢么
我们把所有的$x$放到$y∈[yl,yr]$所构成的$trie$树中，沿着满足题意的出边走，最后访问一下$size$即可。
区间$trie$？我们可以用可持久化$trie$来搞，$size$只要用前缀和减一下就可以了。
代码：
int n,m,tot,a[maxn],b[maxn],s[maxm],t[maxm][2],rt[maxn];
struct rec{int l,r;}c[maxn];
inline void insert(int now,int z)
{
rt[now]=++tot;int x=rt[now],y=rt[now-1];
s[x]=s[y]+1;
for3(i,30,0)
{
int j=z>>i&1;
t[x][j]=++tot;
t[x][j^1]=t[y][j^1];
x=t[x][j];y=t[y][j];
s[x]=s[y]+1;
}
}
int main()
{
n=read();m=read();
for1(i,n)a[i]=read();
for1(i,m)b[i]=read(),insert(i,b[i]);
int T=read();
while(T--)
{
int xl=read(),xr=read(),yl=read(),yr=read(),k=read(),ans=0,now=0;
for2(i,xl,xr)c[i].l=rt[yl-1],c[i].r=rt[yr];
for3(i,30,0)
{
int tmp=0;
for2(j,xl,xr)
{
int k=a[j]>>i&1,p=1;
tmp+=s[t[c[j].r][k!=p]]-s[t[c[j].l][k!=p]];
}
if(now+tmp>=k)
{
ans^=1<<i;
for2(j,xl,xr)
{
int k=a[j]>>i&1,p=1;
c[j].l=t[c[j].l][k!=p];
c[j].r=t[c[j].r][k!=p];
}
}else
{
now+=tmp;
for2(j,xl,xr)
{
int k=a[j]>>i&1,p=0;
c[j].l=t[c[j].l][k!=p];
c[j].r=t[c[j].r][k!=p];
}
}
}
cout<<ans<<endl;
}
return 0;
}
B.平方运算
题意：维护一个数列$a[n]$，有$m$次操作。每次可以：
1）对所有$i∈[l,r]$，执行$a[i]=a[i]*a[i]\%p$
2）输出$\sum_{i=l}^{r}a[i]$ 不对任何数取模
$ n<=100000$ $m<=100000$
每个测试点内的$p$都一样。$20$个$p$分别如下：
$233$ $2332$ $5$ $8192$ $23$ $45$ $37$ $4185$ $5850$ $2975$
$2542$ $2015$ $2003$ $2010$ $4593$ $4562$ $1034$ $5831$ $9905$ $9977$
题解：
首先对于任意$p$，这个问题应该并不可做？
所以问题的可解性一定从$p$的特殊性质入手。
很容易想到是与循环节相关的问题。
$PoPoQQQ$：我们可以打个表，发现任何一个数到环的距离不超过$11$，而且所有环长$LCM$的不超过$60$.
那么想到这一点之后，我们就可以暴力维护$t[k].add[i]$表示线段树$k$所在节点的所有元素被整体平方$i$次之后和为多少。
修改只需要做循环移动即可。
然而还有一个问题就是一开始不一定在环中。
注意到距离很小，所以我们可以在一个数进循环节之前暴力。
具体可以用两颗线段树，一棵用来暴力修改类似于上帝造题的做法，一棵用来维护$add[i]$。
每当一个点进入循环节之后我们就把他加入到另一棵线段树中。
代码：
int n,mx=1,p,v[maxn],b[maxn];
struct seg{int sum,mx;}g[4*maxn];
struct rec{int add[62],tag;}t[4*maxn];
inline void pushup(int k)
{
for0(i,mx-1)t[k].add[i]=t[k<<1].add[i]+t[k<<1|1].add[i];
}
inline void update(int k,int x)
{
for0(i,mx-1)b[i]=t[k].add[i];
for0(i,mx-1)t[k].add[i]=b[(i+x)%mx];
(t[k].tag+=x)%=mx;
}
inline void pushdown(int k)
{
if(!t[k].tag)return;
update(k<<1,t[k].tag);update(k<<1|1,t[k].tag);
t[k].tag=0;
}
inline void insert(int k,int l,int r,int x,int y)
{
if(l==r)
{
t[k].tag=0;
t[k].add[0]=y;
for1(i,mx-1)t[k].add[i]=t[k].add[i-1]*t[k].add[i-1]%p;
return;
}
pushdown(k);
if(x<=mid)insert(lch,x,y);else insert(rch,x,y);
pushup(k);
}
inline void pushupp(int k)
{
g[k].sum=g[k<<1].sum+g[k<<1|1].sum;
g[k].mx=max(g[k<<1].mx,g[k<<1|1].mx);
}
inline void change(int k,int l,int r,int x,int y)
{
if(g[k].mx==0)return;
if(l==x&&r==y)
{
if(l==r)
{
g[k].sum=g[k].sum*g[k].sum%p;
g[k].mx--;
if(g[k].mx==0)
{
insert(1,1,n,l,g[k].sum);
g[k].sum=0;
}
return;
}
change(lch,l,mid);change(rch,mid+1,r);
pushupp(k);
return;
}
if(y<=mid)change(lch,x,y);
else if(x>mid)change(rch,x,y);
else change(lch,x,mid),change(rch,mid+1,y);
pushupp(k);
}
inline void add(int k,int l,int r,int x,int y)
{
if(!t[k].add[0])return;
if(l==x&&r==y){update(k,1);return;}
pushdown(k);
if(y<=mid)add(lch,x,y);
else if(x>mid)add(rch,x,y);
else add(lch,x,mid),add(rch,mid+1,y);
pushup(k);
}
inline int query(int k,int l,int r,int x,int y)
{
if(l==x&&r==y)return g[k].sum+t[k].add[0];
pushdown(k);
if(y<=mid)return query(lch,x,y);
else if(x>mid)return query(rch,x,y);
else return query(lch,x,mid)+query(rch,mid+1,y);
}
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline void build(int k,int l,int r)
{
if(l==r)
{
g[k].sum=read();
int t1=g[k].sum,t2=1;
for(;;)
{
if(v[t1]>0){g[k].mx=v[t1];mx=mx*(t2-v[t1])/gcd(mx,t2-v[t1]);break;}
v[t1]=t2;
t2++;
t1=t1*t1%p;
}
t1=g[k].sum;
for0(i,t2)v[t1]=0,t1=t1*t1%p;
return;
}
build(lch);build(rch);
pushupp(k);
}
int main()
{
n=read();int T=read();p=read();
build(1,1,n);
while(T--)
{
int ch=read(),l=read(),r=read();
if(ch)printf("%d\n",query(1,1,n,l,r));
else add(1,1,n,l,r),change(1,1,n,l,r);
}
return 0;
}
C.解密运算
题意：给出一个长度为$n$权值$∈[1,m]$的数串，在后面加一个$0$。
对这个串进行循环移动$n$次可以得到$n+1$个数串，按字典序排序。
现在给出最后一列，请你求出原串。
$ n<=200000$ $m<=200000$
题解：给出最后一列之后我们排序就可以得到第一列。
这样我们就得到了所有的连续的长度为$2$的连续子串。
那我们再将这些串排序就可以知道第二列，然后依次类推。
这样复杂度是$O（n*m）$。可以拿到$60$分。
我们希望从部分分算法中得到启发，有$20分$是每个数字都不一样。
这样我们可以在得到第一列之后，从特殊字符开始扩充出前面的字符。
满分算法我们仍然考虑这样的做法。
我们拿一个例子来说话：不妨认为最初的串是 $1231240$ 那么得到的$7$个串排序之后是
$0123124$
$1231240$
$1240123$
$2312401$
$2401231$
$3124012$
$4012312$
可以确定的是$0$前面一定是$4$.然后我们发现$40$出现在第$7$行的开头，所以$4$前面一定是$2$.
然后我们又发现$24$出现在第$5$行，那么$2$前面一定是$1$.
然后问题来了，$12$出现在$3 4$ 行，到底哪一个是我们现在的$12$呢。
容易看出，我们每次到一个字符串，都会用它的最后一个数字作为当前答案的第一个数字，然后再用前两个数字去找新的数字。
12作为开头出现了两次，所以一定会作为开头结尾出现两次，而我们如何匹配这两次呢？
因为我们是在不断扩充当前连续的答案数串，那么当这个字符串去掉首尾之后与他匹配的字符串去掉头两个字符应该是完全一样的。
所以只要在对二元数串排序的时候保证完全相同的时候字典序小的排在前面即可。
感觉这题确实不太好说清楚，有问题可以$q$我$973446154$。
代码：
int n,m,a[maxn],b[maxn],c[maxn],d[maxn],ans[maxn];
inline bool cmp(int x,int y)
{
if(a[x]!=a[y])return a[x]<a[y];
else if(b[x]!=b[y])return b[x]<b[y];
else return x<y;
}
int main()
{
n=read();m=read();
for1(i,n+1)a[i]=read(),b[i]=a[i],c[i]=i;
sort(b+1,b+n+2);
sort(c+1,c+n+2,cmp);
for1(i,n+1)d[c[i]]=i;
int now=1;
for3(i,n,1)ans[i]=a[now],now=d[now];
for1(i,n)printf("%d%c",ans[i],i==n?' ':' ');
return 0;
}
评论 (0)
