洛谷P2709小B的询问

莫队裸题，模板题
莫队就是把询问区间排个序，先按左端点的Pos排序（POS是分块那个数组）,pos一样的按右端点排序

代码：

 #include <bits/stdc++.h>

 #define nmax 50010

 using namespace std;

 int a[nmax],ta[nmax],cnt[nmax]={};

 int n,m,qn,k;

 struct que{

     int l,r,p,id;

     bool operator < (const que& x) const{ return (x.p==p)?(x.r>r):(x.p>p); }

 }q[nmax];

 int main(){

     scanf("%d%d%d",&n,&qn,&k);

     m=sqrt(n);

     for (int i=; i<=n; i++) scanf("%d",&a[i]);

     for (int i=; i<=qn; i++) {

         scanf("%d%d",&q[i].l,&q[i].r);

         q[i].p=(q[i].l-)/m;

         q[i].id=i;

     }

     sort(q+,q+qn+);

     int l=q[].l,r=q[].l-,ans=;

     for (int i=; i<=qn; i++) {

         while(l>q[i].l) l--,ans+=(*cnt[a[l]]+),cnt[a[l]]++;

         while(r<q[i].r) r++,ans+=(*cnt[a[r]]+),cnt[a[r]]++;

         while(l<q[i].l) ans-=(*cnt[a[l]]-),cnt[a[l]]--,l++;

         while(r>q[i].r) ans-=(*cnt[a[r]]-),cnt[a[r]]--,r--;

         ta[q[i].id]=ans;

     }

     for (int i=; i<=qn; i++) printf("%d\n",ta[i]);

     return ;

 }

ヽ✿゜▽゜)ノ

BZOJ3289: Mato的文件管理

莫队加树状数组
每次区间长度增加的时候加上移动次数，减少的时候减去本来的移动次数（题意是只能移动相邻的嘛）
移动次数就是在当前区间的排名辣（因为要移动到那里去嘛，这个用树状数组很好维护。
没注意看题目，没有离散化re到死（果然人傻就是有各种各样的问题，嘤）

代码：

 #include <bits/stdc++.h>

 #define lowbit(x) x&(-x)

 #define nmax 50005

 using namespace std;

 typedef long long ll;

 int n,q,bn; //bn为每块的大小

 int data[nmax],c[nmax]={},lsh[nmax];

 ll ans[nmax]={};

 struct seg{

     int l,r,pl,id;

     bool operator < (const seg a) const{ return (a.pl==pl)?(a.r>r):(a.pl>pl); }

 }qes[nmax];

 void upd(int x,int y){ //y决定是加是减

     while(x<=n) { c[x]+=y; x+=lowbit(x); }

 }

 int myfind(int x){

     int ans=;

     while(x>) { ans+=c[x]; x-=lowbit(x); }

     return ans;

 }

 bool mycmp(int a,int b){ return data[a]<data[b]; }

 int main(){

     cin>>n;

     bn=sqrt(n);

     for (int i=; i<=n; i++) { scanf("%d",&data[i]); lsh[i]=i; }

     sort(lsh+,lsh+n+,mycmp);

     for (int i=; i<=n; i++) data[ lsh[i] ]=i;

     cin>>q;

     for (int i=; i<=q; i++) {

         scanf("%d%d",&qes[i].l,&qes[i].r);

         qes[i].id=i;

         qes[i].pl=(qes[i].l-)/bn+;

     }

     sort(qes+,qes+q+);

     int l=qes[].l,r=qes[].l-,nowl=,ta=;  //nowl现在该区间的长度

     for (int i=; i<=q; i++) {

         while(qes[i].l<l) l--,upd(data[l],),ta+=( myfind(data[l])- ),nowl++;

         while(qes[i].r>r) nowl++,r++,upd(data[r],),ta+=( nowl-myfind(data[r]) );

         while(qes[i].l>l) ta-=( myfind(data[l])- ),upd(data[l],-),nowl--,l++;

         while(qes[i].r<r) ta-=( nowl-myfind(data[r]) ),upd(data[r],-),nowl--,r--;

         ans[ qes[i].id ]=ta;

     }

     for (int i=; i<=q; i++) printf("%lld\n",ans[i]);

     return ;

 }

(╯▔皿▔)╯

巴特西

wa自动机的莫队刷题记录

洛谷P2709小B的询问

BZOJ3289: Mato的文件管理

最新文章

热门文章

巴特西

wa自动机 的 莫队 刷题记录

洛谷P2709小B的询问

BZOJ3289: Mato的文件管理

最新文章

热门文章

wa自动机的莫队刷题记录