什么是网站排名优化,新型建筑塑料模板的价格,专业开发网站设计,郑州注册公司需要多少钱题解
题目本身不难想
首先注意到所有查询的序列长度都是小于logn级别的
我们可以枚举序列长度len#xff0c;然后用类似滑动窗口的方法#xff0c;一次性预处理出每种字串的所有出现位置#xff0c;也就是开N个set去维护所有的位置。预处理会进行O(logn)轮#xff0c;每… 题解
题目本身不难想
首先注意到所有查询的序列长度都是小于logn级别的
我们可以枚举序列长度len然后用类似滑动窗口的方法一次性预处理出每种字串的所有出现位置也就是开N个set去维护所有的位置。预处理会进行O(logn)轮每次需要O(n*logn)的时间复杂度初始化set并计算位置。总共复杂度O(nlog^2n)看一下时间限制6s感觉可以过23333。 删除操作可以直接暴力直接从每种字串的位置集合中删除所有被影响到的位置然后再把删除后字符串合并产生的新的子串加入到set中过程中需要支持O(logn)的单点删除和单点查询。 在set中删除起始点在L~R之间子串信息再插入起始点在L到x-1的新构成的子串的信息
删除操作最多O(n/logn)次每次直接暴力就是O(log^2n)总共复杂度O(nlogn)
接下来就是一些小问题如何维护单点删除、单点查询的序列呢
首先我们肯定不会去真正的移动序列保留原始的输入01序列
可以想到用set去维护当前存在的每个坐标但是支持查询第k个坐标的话得手写平衡树
也可以想到用线段树或者树状数组维护每个位置的存在信息在线段树或者树状数组上二分来查询删除后的序列中的第k个坐标的真实位置。 这里使用树状数组
树状数组二分类似于倍增查询LCA的思想十分易懂。 然后我们迅速写完整个内容交一发发现TLE了
看一下复杂度发现瓶颈在于预处理于是我们把初始化中对每个位置都进行树状数组二分替换为直接使用当前位置存在信息数组进行处理这样预处理中计算坐标的部分就变成O(n)了
但是仍然TLE了
现在瓶颈仍然是预处理如果C支持对有序序列O(n)建立set就好了 后来看了洛谷上题解的方法才知道可以用两个优先队列来模拟set
由于我们只需要维护集合中的最小值以及集合的元素个数
使用两个堆一个维护插入的内容另一个维护删除的内容
当查询个数时两个堆的大小相减即可。当查询最小值时如果“删除堆”中的最小值与“插入堆”中的最小值相等就两个一起pop掉直到找到第一个“插入堆”中存在但“删除堆”中不存在的元素即可。
其实也可以用两个vector来模拟因为对于每种子串查询的次数只有一次所以可以大胆排序再查询这样初始化时间复杂度也是O(nlogn)查询删除子串的总时间复杂度是最坏O(nlog^2n)不过似乎也能过因为sort在大部分都有序的情况下还是很快的
改完之后从6.18s变成了1.17s发生了质的飞跃23333
有人可能会问优先队列插入不也是O(logn)的吗为什么会比set快这么多因为预处理的过程中插入集合的内容是顺序的根据小根堆的实现只有当自己比父亲值小时才会发生交换所以在预处理建立小根堆的过程中是O(n)的这样预处理的总复杂度就变成了O(nlogn)删除方面在理论上最坏时间复杂度也是O(nlog^2n)假设所有的位置都集中在一种子串上并且“删除堆”和“插入堆”差不多大
代码
#includecstdio
#includecstring
#includealgorithm
#includeset
#includequeue
using namespace std;
#define N 1000005
#define LOG 20
int n, n_real, now;
char ss[N];
// 树状数组维护单点删除与单点查询的序列
// 实际坐标-逻辑坐标删除后的坐标 getsum
// 逻辑坐标-实际坐标 query 树状数组二分
int tra[N];
int getsum(int x)
{int ret0;for(;x;x-x-x) rettra[x];return ret;
}
void update(int x,int k)
{for(;xn;xx-x)tra[x]k;
}
int query(int k)// 查询删除后序列的第k位置的实际坐标
{int ans0,sum0;for(int iLOG;i0;i--){if(ans(1i)n sumtra[ans(1i)]k){sumtra[ans(1i)];ans(1i);}}return ans1;
}
// a是原始数据tmp是删除后的数组b表示当前位是否存在(树状数组建立在b上)
bool a[N],tmp[N],b[N];
int pos[N];
void cal_tmp_all()
{int cnt0;for(int i1;in;i){if(b[i]){pos[cnt]i;tmp[cnt]a[i];}}
}
void cal_tmp(int l,int r)
{lmax(1,l);rmin(r,n_real);for(int il;ir;i){pos[i]query(i);tmp[i]a[pos[i]];}
}
priority_queueint,vectorint,greaterint S[N],D[N];
//setint S[N];
//setint::iterator it;
// 将起始点在l r之间长度为len的数据加入到set或者从set中删除
void update_set(int l,int r,int len,bool flg)
{rmin(n_real,rlen-1);int lim_l max(now,1(len-1)), lim_r min(n,(1len)-1);int mask(1len)-1;int tmp_value0;for(int il;ir;i){tmp_value((tmp_value1)mask)|tmp[i];if(i-l1 len tmp_valuelim_l tmp_valuelim_r){if(flg)S[tmp_value].push(pos[i-len1]);elseD[tmp_value].push(pos[i-len1]);}}
}
int main()
{scanf(%d,n);n_realn;scanf(%s,ss1);for(int i1;in;i){a[i]int(ss[i]-0);update(i,1);b[i]1;}now1;for(int len1;n(len-1);len){cal_tmp_all();update_set(1,n_real,len,1);//printf(start len:%d\n,len);for(;now(1len);now){//printf(now:%d\n,now);if(nown)return 0;int siz (int)S[now].size()-(int)D[now].size();if(!siz){printf(-1 0\n);continue;}while(!S[now].empty()!D[now].empty() S[now].top()D[now].top()){S[now].pop();D[now].pop();}int xgetsum(S[now].top());printf(%d %d\n,x,siz);int lmax(1,x-len1),rmin(n_real,xlen-1);// 删除受影响的结果cal_tmp(l,rlen-1);update_set(l,r,len,0);// 删除对应的01序列for(int ix;ir;i){update(pos[i],-1);b[pos[i]]0;}n_real-len;// 添加新产生的序列结果cal_tmp(l,x-1len-1);update_set(l,x-1,len,1);while(!S[now].empty())S[now].pop();while(!D[now].empty())D[now].pop();}}
}
