当前位置: 首页 > news >正文

个人做网络推广哪个网站好seo蜘蛛池

个人做网络推广哪个网站好,seo蜘蛛池,铜仁北京网站建设,网站建站侵权怎么办我手把手教她打扑克 qwq 综合分析一下2个操作,查找区间第k小的值,感觉可以用主席树,区间修改那没事了 考虑分块做法,块长B 分析第一个操作 只需要维护数列的单调性,然后二分答案上二分就ok了 分析第二个操作 维护一个加法懒…

我手把手教她打扑克 qwq

综合分析一下2个操作,查找区间第k小的值,感觉可以用主席树,区间修改那没事了

考虑分块做法,块长B

分析第一个操作

只需要维护数列的单调性,然后二分答案上二分就ok了

分析第二个操作

维护一个加法懒标记即可

口胡了一下感觉很简单

仔细分析一下第一个操作

二分找到一个“第k小值”,再进行check,check的过程中散块遍历一遍,整块二分找到最后一个小于等于x的(只有前面部分有贡献),分析一下时间复杂度,预处理 O(\frac{n}{B}*BlogB),(分块完排序),二分答案O(\frac{n}{B}*lognlogV),二分O(\frac{n}{B}*BlogB)

第二个操作

散块可以暴力然后重构,整块上懒标记,时间复杂度O(\frac{n}{B}*B*logB)

总时间复杂度O(m*\frac{n}{B}*lognlogV)    maybe..

应该需要优化?

分析一下二分答案这块,我们不一定要把L定义无穷小,R定义无穷大,可以维护一下区间最大值区间最小值这样可以转化为O(\frac{n}{B}*logn)差不多能卡过去了,我是这样干的,二分剪枝一下

分析一下散块区间加,不一定要O(BlogB)的排序,我们可以把数列分成2块,没有加的和加的,两边其实都是有序的,因此可以用归并排序优化成O(B)

快长最优可能是sqrt(n)logn..

小优化

1.不一定要把散块重构,如果没有询问到,可以不做,我们用线段树区间赋值的思想,修改后标记一下这个块需要重构,等询问的时候问到了再进行重构

void work(int l,int r){int p=pos[l];int q=pos[r];for(int i=p;i<=q;i++){if(re[i]){rebuild(i);re[i]=0;}}
}

2.二分答案优化

    if(k<1 || R-L+1<k){return -1;}

3.块内二分优化

    if(v[id].front()+add[id]>x){//没有比x小的return 0;}if(v[id].back()+add[id]<=x){//都是小于等于x的return r+1;//r-0+1;}

4.维护区间最大值最小值优化

    for(int i=p+1;i<=q-1;i++){//最后一个是最大res=max(res,v[i].back()+add[i]);}for(int i=p+1;i<=q-1;i++){//第一个是最小res=min(res,v[i].front()+add[i]);}

完整代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<cstring>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=1e5+9;
const int B=1e4+9;
namespace Lan {inline string sread() {string s=" ";char e=getchar();while(e==' '||e=='\n')e=getchar();while(e!=' '&&e!='\n')s+=e,e=getchar();return s;}inline void swrite(string s){for(char e:s)putchar(e);printf("\n");}inline ll read() {ll x=0,y=1;char c=getchar();while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*=y;}inline void write(ll x) {if(x<0){x=-x,putchar('-');}ll sta[35],top=0;do sta[top++]=x%10,x/=10;while(x);while(top)putchar(sta[--top]+'0');}
}using namespace Lan;
ll a[N];
int L[B],R[B],pos[N];
ll add[B];
int re[B];
vector<ll> v[B];
inline void rebuild(int id){v[id].clear();for(int i=L[id];i<=R[id];i++){v[id].push_back(a[i]);}sort(v[id].begin(),v[id].end());
}
inline int binary(int id,int x){int l=0,r=v[id].size()-1;if(v[id].front()+add[id]>x){//没有比x小的return 0;}if(v[id].back()+add[id]<=x){//都是小于等于x的return r+1;//r-0+1;}int res=0;while(l<=r){int mid=(l+r)>>1;if(v[id][mid]+add[id]<=x){//小于等于x,选大一点l=mid+1;res=mid+1;//小于等于x的有贡献}else{r=mid-1;}}return res;
}
inline ll getmax(int l,int r){ll res=-INF;int p=pos[l];int q=pos[r];if(p==q){for(int i=l;i<=r;i++){res=max(res,a[i]+add[pos[i]]);}}else{for(int i=l;i<=R[p];i++){res=max(res,a[i]+add[pos[i]]);}for(int i=L[q];i<=r;i++){res=max(res,a[i]+add[pos[i]]);}for(int i=p+1;i<=q-1;i++){//最后一个是最大res=max(res,v[i].back()+add[i]);}}   return res;
}
inline ll getmin(int l,int r){ll res=INF;int p=pos[l];int q=pos[r];if(p==q){for(int i=l;i<=r;i++){res=min(res,a[i]+add[pos[i]]);}}else{for(int i=l;i<=R[p];i++){res=min(res,a[i]+add[pos[i]]);}for(int i=L[q];i<=r;i++){res=min(res,a[i]+add[pos[i]]);}for(int i=p+1;i<=q-1;i++){//第一个是最小res=min(res,v[i].front()+add[i]);}}return res;
}
inline int check(int l,int r,int x){int p=pos[l];int q=pos[r];int res=0;if(p==q){for(int i=l;i<=r;i++){if(a[i]+add[pos[i]]<=x){res++;}}}else{for(int i=l;i<=R[p];i++){if(a[i]+add[pos[i]]<=x){res++;}}for(int i=L[q];i<=r;i++){ if(a[i]+add[pos[i]]<=x){res++;}}for(int i=p+1;i<=q-1;i++){res+=binary(i,x);}}return res;
}
void work(int l,int r){int p=pos[l];int q=pos[r];for(int i=p;i<=q;i++){if(re[i]){rebuild(i);re[i]=0;}}
}
inline int kth(int k,int L,int R){if(k<1 || R-L+1<k){return -1;}work(L,R);int res=-1;ll l=getmin(L,R),r=getmax(L,R);while(l<=r){ll mid=(l+r)>>1;if(check(L,R,mid)<k){//选的值太小l=mid+1;}else{r=mid-1;res=mid;}}return res;
}
inline void modify(int l,int r,int k){int p=pos[l];int q=pos[r];if(p==q){for(int i=l;i<=r;i++){a[i]+=k;}re[p]=1;// rebuild(p);}else{for(int i=l;i<=R[p];i++){a[i]+=k;}re[p]=1;// rebuild(p);for(int i=p+1;i<=q-1;i++){add[i]+=k;}for(int i=L[q];i<=r;i++){a[i]+=k;}re[q]=1;// rebuild(q);}
}
int main(){// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);int n,m;n=read();m=read();for(int i=1;i<=n;i++){a[i]=read();}int blo=sqrt(n);int t=ceil(1.0*n/blo);for(int i=1;i<=t;i++){L[i]=(i-1)*blo+1;R[i]=(i==t?n:i*blo);}for(int i=1;i<=t;i++){for(int j=L[i];j<=R[i];j++){pos[j]=i;}}for(int i=1;i<=n;i++){v[pos[i]].push_back(a[i]);}for(int i=1;i<=t;i++){sort(v[i].begin(),v[i].end());}for(int i=1;i<=m;i++){int op,l,r,k;op=read();l=read();r=read();k=read();if(op==1){write(kth(k,l,r));putchar('\n');}else{modify(l,r,k);}}return 0;
}

http://www.zhongyajixie.com/news/19008.html

相关文章:

  • 济南怎样做网站推广中国楼市最新消息
  • 自己做网站代码做网站需要哪些技术
  • 隆尧网站制作识图
  • 山东卓创网络网站建设软文写作什么意思
  • 深圳电子商城网站建设搜索广告是什么
  • 百度收录哪个网站多武汉大学人民医院洪山院区
  • 学做网站论坛vip账号全国疫情最新数据
  • wordpress重定向代码湖北seo
  • 做网站建设费用如何用html制作网页
  • 杭州网站制百度手机助手安卓版下载
  • 深圳疫情通报最新消息深圳防疫措施优化
  • 网站运营适合什么样的人做网站底部友情链接代码
  • icp备案是什么怎么卸载windows优化大师
  • 做企业网站可以没有后台吗网站搭建需要什么
  • 做网站1000以下哪家好写文的免费软件
  • 各种网站推广是怎么做的国内新闻最新5条
  • app网站制作美国传销网站关键词
  • wordpress statraq重庆的seo服务公司
  • 个人做淘宝客网站要备案官网设计比较好看的网站
  • pc端网站转手机站怎么做小说搜索风云榜
  • 营销型网站建设企业北京百度推广开户
  • 学做漂亮早餐的网站哪个网站是免费的
  • 做网站的公司都有哪些岗位站长联盟
  • 做弹弓教程网站全网营销系统怎么样
  • 自己做网站前端开发常用的关键词挖掘工具有哪些
  • 房地产公司名称大全谷歌seo查询
  • 同企网站建设做网站网站站长工具
  • 个人做财经类网站北京seo服务销售
  • 网站备案最快多久哈尔滨seo优化
  • description 网站描述下载百度app下载