作业-[luogu4396][AHOI2013]-莫队
2024-09-06 11:01:25
<题面>
卡常终究比不上算法的优化……
这是莫队的有点小坑的题,
首先不一定能想到,想到不一定打对,打对不一定打好。
首先你会发现,这个题的时限是很长的~
$n$和$m$也是很大的。
于是我们可以计算一个时间复杂度,顺便搞一个块长。
首先有$\Theta (M)$的询问,设块长为$L$,
于是左端点移动,不跨块,移动不超过$L$
右端点移动$N$
然后就有左面的总共移动$M \times L $
右面的移动$\frac{N}{L}\times N$这里应该就是说,每次要挪一个 $N$,而左端点只挪$\frac{N}{L}$次。
(转移一会再算)
这样莫队总复杂度:$\Theta(M \times L + \frac{N^2}{L})$
所以当块长为$\sqrt{\frac{N^2}{M}}=\frac{N}{\sqrt{M}}$时复杂度是最优的(基本不等式)
然后我们想转移,他让我们求一个区间数的个数。
那么,我们就可以用个数据结构,来维护$[a,b]$中数的个数和去重后的数个数
仔细算下,$\log N$的时间复杂度还能承受。
所以选择树状数组或是线段树(常数有点大,用zkw好一些(但是用线段树的A的很困难~))
维护权值。
这样就可以通过用树状数组前缀和或是线段树区间查询解决转移问题。
总复杂度:$\Theta(N\sqrt{M}\log N)$
跑得还好说。
(有人说分块也行,大家加油咯!)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 101101
#define LL long long //#include "debug.h" using namespace std;
struct QUERY{
int l,r,a,b,t;
LL ans1,ans2;
}query[N*10];
int num[N];
int pre[N],n,qn,sqn;
int inpart[N];
int tot[N],pretot[N];
inline int lowbit (int x){ return x&(-x); }
inline int getpart(int x){ return (x-1)/sqn+1; }
LL sum (int x){
LL s=0;
for(int i=x;i;i-=lowbit(i)) s+=pre[i];
return s;
}
LL gettot (int x){
LL s=0;
for(int i=x;i;i-=lowbit(i)) s+=pretot[i];
return s;
}
void chatot (int pos,int x){
while(pos<=n){
pretot[pos]+=x;
pos+=lowbit(pos);
}
}
void change (int pos,int x){
if(tot[pos]==1&&x==-1)
chatot(pos,-1);
else if(tot[pos]==0&&x== 1)
chatot(pos,1);
tot[pos]+=x;
while(pos<=n){
pre[pos]+=x;
pos+=lowbit(pos);
}
}
//bool CMP (const QUERY &a,const QUERY &b){
// if(inpart[a.l]==inpart[b.r])
// return a.r<b.r;
// return a.l<a.l;
//}
bool CMP(const QUERY &x,const QUERY &y){
return inpart[x.l]<inpart[y.l]||(inpart[x.l]==inpart[y.l]&&(inpart[x.l]&1?x.r<y.r:x.r>y.r));
}
bool Cmp (const QUERY &a,const QUERY &b){
return a.t<b.t;
}
int main (){
int a,b,c,d;
scanf("%d%d",&n,&qn);sqn=sqrt(1ll*n*n/qn)+1;
for(int i=1;i<=n;i++){
scanf("%d",num+i);
inpart[i]=getpart(i);
}
for(int i=1;i<=qn;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
query[i].l=a,query[i].r=b,query[i].t=i;
query[i].a=c,query[i].b=d;
}
sort(query+1,query+qn+1,CMP);
//for(int i=1;i<=qn;i++)cout<<query[i].l<<" "<<query[i].r<<endl;
int l=1,r=1,ql,qr;
change(num[1],1);
for(int i=1;i<=qn;i++){//pour(tot,1,n,3,"Tot");
ql=query[i].l,qr=query[i].r,
a =query[i].a,b =query[i].b;
while(l<ql)change(num[l] ,-1),l++;
while(l>ql)change(num[l-1], 1),l--;
while(r<qr)change(num[r+1], 1),r++;
while(r>qr)change(num[r] ,-1),r--;
query[i].ans1=sum(b)-sum(a-1);
query[i].ans2=gettot(b)-gettot(a-1);
}
sort(query+1,query+qn+1,Cmp);
for(int i=1;i<=qn;i++)
printf("%lld %lld\n",query[i].ans1,query[i].ans2);
return 0;
}
最新文章
- 3-udev
- TeamCity : 安装 Agent
- log4net部分配置说明
- 用c#开发微信 (6) 微渠道 - 推广渠道管理系统 1 基础架构搭建
- iOS开发——XML/JSON数据解析
- RZ10
- Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 1) A. Bear and Poker 分解
- T4文本模板
- VR全景:720全景在线购物点亮你的眼球
- Ambari安装之部署 (Metrics Collector和 Metrics Monitor) Install Pending ...问题
- Spring对Bean装配详解
- [转载]领域驱动设计(Domain Driven Design)参考架构详解
- [UE4]小地图UI放在哪里创建合适?
- C++STL 函数对象和谓词
- Innodb页面存储结构-2
- android 工具类 数据库管理
- cent7.0 mysql 修改端口
- [HihoCoder1596]Beautiful Sequence
- poj 1930 Dead Fraction(循环小数化分数)
- Java实现中文算数验证码(算数运算+-*/)
热门文章
- Array.prototype.splice()
- Python 变量与数据类型
- Spring Cloud Alibaba发布第二个版本,Spring 发来贺电
- BZOJ 1579 [Usaco2009 Feb]Revamping Trails 道路升级
- Zuul的容错与回退与Zuul的高可用
- Android基础控件EditText
- Mac OS X 下有关adb相关问题
- Linux RHEL7(CentOS7源) 安装 Nginx
- MyBatis注解开发-@Insert和@InsertProvider(转)
- [原创]关于时间格式的坑(kk:mm:ss、HH:mm:ss与hh:mm:ss)