1.14
数列分块
1.数列分块3：区间加减+区间询问x的前驱（严格小于）
思路：同2，询问时边角暴力，块内需要保持有序，进行二分查找第一个小于c的数。注意两点：
1.边角暴力的时候是对v操作，块内二分是对blk操作。
2.块内二分时找到之后更新答案记得加上lazy[i]。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
#define lf(x) ((x)-1)*bl_size+1
#define rt(x,n) min((x)*bl_size,(n))
const int M=2e5+20,P=1e9+7;
int n,bl_size,blnum[M],lazy[M],v[M];
vector<int> blk[M];
inline void reset(int x){
blk[x].clear();
for(int i=lf(x);i<=rt(x,n);++i)
blk[x].push_back(v[i]);
sort(blk[x].begin(),blk[x].end());
}
inline void bl_init(int n){
bl_size=sqrt(n);
for(int i=1;i<=n;++i)
blnum[i]=(i-1)/bl_size+1,blk[blnum[i]].push_back(v[i]);
for(int i=blnum[1];i<=blnum[n];++i)
sort(blk[i].begin(),blk[i].end());
}
inline void bl_add(int l,int r,int c){
for(int i=l;i<=rt(blnum[l],r);++i)
v[i]+=c;
reset(blnum[l]);
if (blnum[l]!=blnum[r]){
for(int i=lf(blnum[r]);i<=r;++i)
v[i]+=c;
reset(blnum[r]);
}
for(int i=blnum[l]+1;i<=blnum[r]-1;++i)
lazy[i]+=c;
}
inline int query(int l,int r,int c){
int ans=-1;
for(int i=l;i<=rt(blnum[l],r);++i)
if (v[i]+lazy[blnum[l]]<c)
ans=max(ans,v[i]+lazy[blnum[l]]);
if (blnum[l]!=blnum[r])
for(int i=lf(blnum[r]);i<=r;++i)
if (v[i]+lazy[blnum[r]]<c)
ans=max(ans,v[i]+lazy[blnum[r]]);
for(int i=blnum[l]+1;i<=blnum[r]-1;++i){
vector<int>::iterator pos=lower_bound(blk[i].begin(),blk[i].end(),c-lazy[i]);
if (pos!=blk[i].begin())
--pos,ans=max(ans,(*pos)+lazy[i]);//注意
}
return ans;
}
struct TTTT{
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&v[i]);
bl_init(n);
}
void run(){
init();
for(int i=1;i<=n;++i){
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0)
bl_add(l,r,c);
else
printf("%d
",query(l,r,c));
}
}
}TTT;
int main(){
TTT.run();
return 0;
}
2.数列分块4：区间加减+区间求和
要注意lazy标记的含义，表示懒得加，区间修改并不直接加到sum里面。另外记得开LL。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define lf(x) ((x)-1)*bl_size+1
#define rt(x,n) min((x)*bl_size,(n))
#define Blforl(l,r) for(int i=(l);i<=rt(blnum[(l)],(r));++i)
#define Blforr(l,r) for(int i=lf(blnum[(r)]);i<=(r);++i)
#define Blforbl(l,r) for(int i=blnum[(l)]+1;i<=blnum[(r)]-1;++i)
const int M=1e5+20;
int n,bl_size;//整体信息
int blnum[M];
LL v[M];//单点信息
LL lazy[M],sum[M];//整块信息
inline void bl_init(){
bl_size=sqrt(n);
for(int i=1;i<=n;++i)
blnum[i]=(i-1)/bl_size+1,sum[blnum[i]]+=v[i];
}
inline void add(int l,int r,int c){
Blforl(l,r)
v[i]+=c,sum[blnum[i]]+=c;
if (blnum[l]!=blnum[r])
Blforr(l,r)
v[i]+=c,sum[blnum[i]]+=c;
Blforbl(l,r)
lazy[i]+=c;
}
inline LL query(int l,int r){
LL ans=0;
Blforl(l,r)
ans+=v[i]+lazy[blnum[i]];
if (blnum[l]!=blnum[r])
Blforr(l,r)
ans+=v[i]+lazy[blnum[i]];
Blforbl(l,r)
ans+=sum[i]+lazy[i]*bl_size;
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&v[i]);
bl_init();
for(int i=1;i<=n;++i){
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if (op==0)
add(l,r,c);
else
printf("%lld
",query(l,r)%(c+1));
}
return 0;
}
3.数列分块5：区间开方+区间求和。
对于区间开方的问题，要注意到开logn次之后就会都变成0和1，因此直接暴力区间修改也是ok的，这是因为每个点最多开32次根就变成0或1的。但是为了防止每次判断是否已经是0和1的时候每个元素都访问，所以可以采用分块优化的策略。边角暴力，块内先看flag，如果已经全是01就跳过，否则就暴力修改。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define lf(x) ((x)-1)*bl_size+1
#define rt(x,n) min((x)*bl_size,(n))
#define Blforl(l,r) for(int i=(l);i<=rt(blnum[(l)],(r));++i)
#define Blforr(l,r) for(int i=lf(blnum[(r)]);i<=(r);++i)
#define Blforx(x) for (int i=lf(x);i<=rt(x);++i)
#define Blforbl(l,r) for(int i=blnum[(l)]+1;i<=blnum[(r)]-1;++i)
const int M=1e5+20;
int n,bl_size;//整体信息
int blnum[M],v[M];//单点信息
int flag[M],sum[M];//整块信息
inline void bl_init(){
bl_size=sqrt(n);
for(int i=1;i<=n;++i)
blnum[i]=(i-1)/bl_size+1,sum[blnum[i]]+=v[i];
for(int i=1;i<=blnum[n];++i)
flag[i]=1;
}
inline void blsqrt(int l,int r){
Blforl(l,r)
sum[blnum[i]]-=v[i],v[i]=sqrt(v[i]),sum[blnum[i]]+=v[i];
if (blnum[l]!=blnum[r])
Blforr(l,r)
sum[blnum[i]]-=v[i],v[i]=sqrt(v[i]),sum[blnum[i]]+=v[i];
Blforbl(l,r){
if (!flag[i])
continue;
flag[i]=sum[i]=0;
for(int j=lf(i);j<=rt(i,r);++j){
v[j]=sqrt(v[j]),sum[i]+=v[j];
if(v[j]>1)
flag[i]=1;
}
}
}
inline LL query(int l,int r){
LL ans=0;
Blforl(l,r)
ans+=v[i];
if (blnum[l]!=blnum[r])
Blforr(l,r)
ans+=v[i];
Blforbl(l,r)
ans+=sum[i];
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&v[i]);
bl_init();
for(int i=1;i<=n;++i){
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if (op==0)
blsqrt(l,r);
else
printf("%lld
",query(l,r));
}
return 0;
}
2020WannaflyD3
A. 黑色气球
思路：水题，上三角矩阵和是n*(sigma)，之后减去第一行得a1，再用第一行求解即可。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int a[2000][2000];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]);
if (n==2){
printf("1 1
");
return 0;
}
LL sum=0;
for(int i=1;i<=n-1;++i)
for(int j=i+1;j<=n;++j)
sum+=a[i][j];
sum/=n-1;
LL sum2=0;
for(int i=1;i<=n;++i)
sum2+=a[1][i];
sum2=(sum2-sum)/(n-2);
printf("%lld",sum2);
for(int i=2;i<=n;++i)
printf(" %lld",a[1][i]-sum2);
cout<<endl;
return 0;
}
E. 棋技哥
C. 无向图定向
思路：答案=最小染色数-1
D. 求和
思路：推式子
[Sigma_{i=1}^nSigma_{j=1}^iSigma_{k=1}^igcd(i,j,k)\
=Sigma_{d=1}^ndSigma_{i=1}^nSigma_{j=1}^iSigma_{k=1}^i[gcd(i,j,k)==d]\
=Sigma_{d=1}^ndSigma_{i=1}^{lfloorfrac{n}{d}
floor}Sigma_{j=1}^iSigma_{k=1}^i[gcd(i,j,k)==1]（注意i是不改变的）\
=Sigma_{d=1}^ndSigma_{i=1}^{lfloorfrac{n}{d}
floor}Sigma_{j=1}^iSigma_{k=1}^iSigma_{e|i,e|j,e|k}mu(e)\
=Sigma_{d=1}^ndSigma_{e=1}^{lfloorfrac{n}{d}
floor}mu(e)Sigma_{i=1}^{lfloorfrac{n}{d}
floor}Sigma_{j=1}^iSigma_{k=1}^i\
]
G. 火山哥周游世界
思路：虚树和最远点？
分两类讨论
F. 社团管理
思路：决策单调。整体二分。
I. N门问题
思路：无论打开了哪扇门，A选择的门在打开之后都会变成全场唯一概率最小的门。
H. 火山哥的序列
思路：保证数据互不相同，是用来枚举倍数的，这样就可以保证复杂度是nlogn。
J. 简单字符串
Lyndon串：s的最小后缀是本身。
Lyndon分解：任意串可以划分为一堆Lyndon串，v1q1,v2q1...
且v1>v2>...>vm
存在性和唯一性
若q1%k!=0
v1 q1/k
q1/k!=0
v1 q1/k v2q2 v3 q3 ……
只用算Lyndon分解的v1和q1即可。
Edu 80
A.Deadline
题意：给定d和n，问是否存在x，使得x+(lfloorfrac{d}{x+1} floor)<=n
思路：容易想到，在x+1>(sqrt{d})之后(或者多几个数)，就都一样了，所以只需要暴力判(1simsqrt{d}+100)即可。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=2e5+20,P=1e9+7;
struct TTTT{
int n,d;
void init(){
scanf("%d%d",&n,&d);
}
void run(){
init();
int x=0,lim=min((int)sqrt(d)+100,n);
while(x<=lim){
if (x+(d+x)/(x+1)<=n){
printf("YES
");
return;
}
++x;
}
printf("NO
");
}
}TTT;
int main(){
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i)
TTT.run();
return 0;
}
B.Yet Another Meme Problem
题意：给定A和B，统计(1leq aleq A)且(1leq bleq B)a⋅b+a+b=conc(a,b)的对数。
思路：b+1=10^|b|，直接统计即可。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=2e5+20,P=1e9+7;
struct TTTT{
int a,b;
void init(){
scanf("%d%d",&a,&b);
}
int dig(int x){
int ans=0;
while(x)
x/=10,++ans;
return ans;
}
void run(){
init();
printf("%lld
",1LL*a*(dig(b+1)-1));
}
}TTT;
int main(){
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i)
TTT.run();
return 0;
}
C.Two Arrays
题意：给定n和m，统计数列(a,b)的个数，满足长度均为m，元素范围1-n，(a_ileq b_i)，a不降，b不升。
思路：我是dp做法，但实际上看题解其实很简单，考虑(a_1,a_2,...,a_m,b_m,b_{m-1},...,b_1)，这个序列就是不降序列，所以直接统计这个序列的个数就可以，算就行。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=2e5+20,P=1e9+7;
struct TTTT{
int n,m,dp[15][3000];
void init(){
scanf("%d%d",&n,&m);
}
void run(){
init();
for(int i=0;i<=n-1;++i)
dp[1][i]=n-i;
for(int i=2;i<=m;++i)
for(int j=0;j<=n-1;++j)
for(int k=0;j+k<=n-1;++k)
dp[i][j]=(dp[i][j]+1LL*dp[i-1][j+k]*(k+1)%P)%P;
int ans=0;
for(int i=0;i<=n-1;++i)
ans=(ans+dp[m][i])%P;
printf("%d
",ans);
}
}TTT;
int main(){
TTT.run();
return 0;
}
D.Minimax Problem
题意：给定n个长度为m的数组，可以选择两个数组合成一个新的数组，新的数组的每个数都是原来两个数组的对应位置的最大值，现求新的数组最小值最大的情况下，要选的两个数组的位置。
思路：二分最小值，设为k，将矩阵中(geq k)设为1，(<k)的设为0，那么就会得到n个字节长度为m的数，现在只需要查看是否存在两个数，使得|操作之后为全1。由于不同数个数最多为(2^m)，因此直接(n^2)暴力判即可。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mid ((l+r+1)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=3e5+20,P=1e9+7;
struct TTTT{
int n,m;
int a[M][10];
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
}
void run(){
init();
int l=0,r=1e9;
int num[300],lim=(1<<m)-1;
while(l!=r){
for(int i=0;i<=lim;++i)
num[i]=0;
for(int i=1;i<=n;++i){
int ans=0;
for(int j=1;j<=m;++j)
ans=(ans<<1)+((a[i][j]>=mid)?1:0);
/*db(mid);
db(i);
db(ans);*/
++num[ans];
}
bool v=false;
for(int i=lim;i>=0;--i){
for(int j=lim;j>=0;--j)
if (num[i]&&num[j]&&((i|j)==lim)){
v=true;
break;
}
if (v)
break;
}
if (v)
l=mid;
else
r=mid-1;
}
//db(l);
vector<int> v[300];
for(int i=1;i<=n;++i){
int ans=0;
for(int j=1;j<=m;++j)
ans=(ans<<1)+((a[i][j]>=l)?1:0);
v[ans].push_back(i);
}
for(int i=lim;i>=0;--i)
for(int j=lim;j>=0;--j)
if (v[i].size()&&v[j].size()&&((i|j)==lim)){
printf("%d %d
",v[i][0],v[j][0]);
return;
}
}
}TTT;
int main(){
TTT.run();
return 0;
}
E.Messenger Simulator
题意：现有一个1-n的序列，给了m个数，每次将这个数提到序列的最前面，问每个数所能达到的最靠前位置和最靠后位置。
思路：设原序列为空，那么操作序列可以等价为：(n,n-1,...,2,1,a_1,a_2,...,a_m)，观察这个序列，考虑数k，如果在后m个数中出现了k，那么k的最小值就是1，否则就是k本身（因为移动其他数一定不会让k的位置更靠前）。至于最大值，则是序列中相邻k构成区间的区间不同数的个数，相当于两次之间有多少个数被提到了k的前面，除了所有k出现的位置构成的相邻区间，k的最后一次出现位置和(a_m)构成的区间的不同数个数也要统计进来（感性写个例子理解一下）。那么就变成了区间不同数问题，而且可以离线做，因此树状数组即可。我傻不拉几写了个主席树，最后还因为数组没有开大挂了……
注意：主席树一定要预估好数组大小。如果数组越界，只要没有访问到系统内存，那么是不会报RE的，所以有可能访问到已经用过的内存，造成错误，会出现各种各样的WA，TLE，MLE等等奇怪的错误。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=2e7+10,P=998244353,MM=6e5+20;//96M，不用怕MLE
int cnt;
int a[MM],root[MM*2],L[M],R[M],v[M],last[MM],rtn[MM],nxt[MM],vis[MM],ansmn[MM],ansmx[MM],num[MM];
int build(int l,int r){
int rt=++cnt,mid=(l+r)/2;
v[rt]=0;
if (l==r)
return rt;
L[rt]=build(l,mid);
R[rt]=build(mid+1,r);
return rt;
}
int update(int idp,int l,int r,int pos,int x){
int rt=++cnt,mid=(l+r)/2;
L[rt]=L[idp],R[rt]=R[idp];
if (x)
v[rt]=v[idp]+1;
else
v[rt]=v[idp]-1;
if (l==r)
return rt;
if (pos<=mid)
L[rt]=update(L[idp],l,mid,pos,x);
if (mid<pos)
R[rt]=update(R[idp],mid+1,r,pos,x);
return rt;
}
int query1(int idp,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr)
return v[idp];
int ans=0,mid=(l+r)/2;
if (ql<=mid)
ans+=query1(L[idp],l,mid,ql,qr);
if (mid<qr)
ans+=query1(R[idp],mid+1,r,ql,qr);
return ans;
}
int main(){
int n,m;
//freopen("out.txt","w",stdout);
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
a[i]=n-i+1;
for(int i=1;i<=m;++i)
scanf("%d",&a[i+n]),++num[a[i+n]];
root[0]=build(1,n+m);
int ccnt=0;
for (int i=1;i<=n+m;++i){
if (last[a[i]])
root[ccnt+1]=update(root[ccnt],1,n+m,last[a[i]],0),++ccnt;
root[ccnt+1]=update(root[ccnt],1,n+m,i,1),++ccnt;
nxt[last[a[i]]]=i,last[a[i]]=i;
rtn[i]=ccnt;
}
for (int i=1;i<=n+m;++i){
if (vis[a[i]])
continue;
vis[a[i]]=1;
if (num[a[i]]>0)
ansmn[a[i]]=1;
int p=i;
while(nxt[p])
ansmx[a[i]]=max(ansmx[a[i]],query1(root[rtn[nxt[p]]],1,n+m,p,nxt[p])),p=nxt[p];
ansmx[a[i]]=max(ansmx[a[i]],query1(root[rtn[n+m]],1,n+m,p,n+m));
}
for(int i=1;i<=n;++i)
printf("%d %d
",ansmn[i]?ansmn[i]:i,ansmx[i]);
return 0;
}