整体二分QAQ

时间：2022-05-24 04:55:47

POJ 2104 K-th Number

时空隧道

题意：

给出一个序列，每次查询区间第k小

分析：

整体二分入门题？

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 //by NeighThorn

 #define inf 0x3f3f3f3f

 using namespace std;

 const int maxn=+,maxm=+;

 int n,m,a[maxn],ans[maxm],tr[maxn];

 struct M{

     int x,y,k,id,flag;

     M(int a=,int b=,int c=,int d=,int e=){

         x=a,y=b,k=c,id=d,flag=e;

     }

 }q[maxm+maxn],q1[maxm+maxn],q2[maxm+maxn];

 inline void add(int x,int y){

     for(;x<=n;x+=x&(-x))

         tr[x]+=y;

 }

 inline int query(int x){

     int res=;

     for(;x;x-=x&(-x))

         res+=tr[x];

     return res;

 }

 inline void solve(int L,int R,int l,int r){

     if(L>R)

         return;

     if(l==r){

         for(int i=L;i<=R;i++)

             if(q[i].flag==)

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

         return;

     }

     int mid=(l+r)>>,l1=,l2=;

     for(int i=L;i<=R;i++){

         if(q[i].flag==){

             if(q[i].x<=mid)

                 add(q[i].id,),q1[l1++]=q[i];

             else

                 q2[l2++]=q[i];

         }

         else{

             int lala=query(q[i].y)-query(q[i].x-);

             if(lala>=q[i].k)

                 q1[l1++]=q[i];

             else

                 q[i].k-=lala,q2[l2++]=q[i];

         }

     }

     for(int i=;i<l1;i++)

         if(q1[i].flag==)

             add(q1[i].id,-);

     memcpy(q+L,q1,sizeof(q[])*l1);

     memcpy(q+L+l1,q2,sizeof(q[])*l2);

     solve(L,L+l1-,l,mid);solve(L+l1,R,mid+,r);

 }

 signed main(void){

     while(scanf("%d%d",&n,&m)!=EOF){

         memset(tr,,sizeof(tr));

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

             scanf("%d",&a[i]);

             q[i]=(M){a[i],,,i,};

         }

         for(int i=;i<=m;i++)

             scanf("%d%d%d",&q[i+n].x,&q[i+n].y,&q[i+n].k),q[i+n].id=i,q[i+n].flag=;

         solve(,n+m,-inf,inf);

         for(int i=;i<=m;i++)

             printf("%d\n",ans[i]);

     }

     return ;

 }

BZOJ 1901: Zju2112 Dynamic Rankings

时空隧道

分析：

和上一题一样，就是把修改操作拆成删除和插入操作...

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 //by NeighThorn

 #define inf 0x3f3f3f3f

 using namespace std;

 const int maxn=+;

 int n,m,cnt,tot,tr[maxn],pre[maxn],ans[maxn];

 char ch[];

 struct M{

     int x,y,k,id,flag;

 }q[maxn*],q1[maxn*],q2[maxn*];

 inline int read(void){

     char ch=getchar();int f=,x=;

     while(!(ch>=''&&ch<='')){

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

         x=x*+ch-'',ch=getchar();

     return x;

 }

 inline void insert(int x,int y){

     for(;x<=n;x+=x&(-x))

         tr[x]+=y;

 }

 inline int query(int x){

     int res=;

     for(;x;x-=x&(-x))

         res+=tr[x];

     return res;

 }

 inline void solve(int L,int R,int l,int r){

     if(L>R)

         return;

     if(l==r){

         for(int i=L;i<=R;i++)

             if(q[i].flag==)

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

         return;

     }

     int mid=(l+r)>>,l1=,l2=;

     for(int i=L;i<=R;i++){

         if(q[i].flag==){

             if(q[i].x<=mid)

                 insert(q[i].id,q[i].y),q1[l1++]=q[i];

             else

                 q2[l2++]=q[i];

         }

         else{

             int lala=query(q[i].y)-query(q[i].x-);

             if(lala>=q[i].k)

                 q1[l1++]=q[i];

             else

                 q[i].k-=lala,q2[l2++]=q[i];

         }

     }

     for(int i=;i<l1;i++)

         if(q1[i].flag==)

             insert(q1[i].id,-q1[i].y);

     memcpy(q+L,q1,sizeof(q[])*l1);

     memcpy(q+L+l1,q2,sizeof(q[])*l2);

     solve(L,L+l1-,l,mid);solve(L+l1,R,mid+,r);

 }

 signed main(void){

     n=read(),m=read();tot=n;

     for(int i=;i<=n;i++)

         pre[i]=read(),q[i].x=pre[i],q[i].y=,q[i].k=,q[i].id=i,q[i].flag=;

     for(int i=,x,y;i<=m;i++){

         scanf("%s",ch);tot++;

         if(ch[]=='Q')

             q[tot].x=read(),q[tot].y=read(),q[tot].k=read(),q[tot].id=++cnt,q[tot].flag=;

         else

             x=read(),y=read(),q[tot].x=pre[x],q[tot].y=-,q[tot].k=,q[tot].id=x,q[tot].flag=,

             pre[x]=y,q[++tot].x=y,q[tot].y=,q[tot].k=,q[tot].id=x,q[tot].flag=;

     }

     solve(,tot,,inf);

     for(int i=;i<=cnt;i++)

         printf("%d\n",ans[i]);

     return ;

 }//Cap ou pas cap. Cap.

BZOJ 3110: [Zjoi2013]K大数查询

时空隧道

分析：

还是一样的...只是把树状数组改成了线段树...

然而...虽然题水...但是我WA了半页...快读写错了...没有读入负数

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 //by NeighThorn

 #define int long long

 using namespace std;

 const int maxn=+;

 int n,m,cnt,ans[maxn];

 struct M{

     int x,y,id,flag;

     long long k;

 }q[maxn],q1[maxn],q2[maxn];

 struct Tree{

     int l,r;

     long long sum,lazy;

 }tree[maxn<<];

 inline long long longread(void){

     char ch=getchar();int f=;long long x=;

     while(!(ch>=''&&ch<='')){

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

         x=x*+ch-'',ch=getchar();

     return f*x;

 }

 inline int intread(void){

     char ch=getchar();int f=,x=;

     while(!(ch>=''&&ch<='')){

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

         x=x*+ch-'',ch=getchar();

     return f*x;

 }

 inline void build(int l,int r,int tr){

     tree[tr].l=l,tree[tr].r=r,tree[tr].sum=,tree[tr].lazy=;

     if(l==r)

         return;

     int mid=(l+r)>>;

     build(l,mid,tr<<),build(mid+,r,tr<<|);

 }

 inline void change(int l,int r,int val,int tr){//cout<<l<<" "<<r<<"   "<<tree[tr].l<<" "<<tree[tr].r<<" "<<tr<<"   ";

     if(tree[tr].l==l&&tree[tr].r==r){

         tree[tr].sum+=val*(r-l+);

         tree[tr].lazy+=val;return;

     }

     int mid=(tree[tr].l+tree[tr].r)>>;//cout<<mid<<endl;

     if(tree[tr].lazy)

         change(tree[tr].l,mid,tree[tr].lazy,tr<<),change(mid+,tree[tr].r,tree[tr].lazy,tr<<|),tree[tr].lazy=;

     if(r<=mid)

         change(l,r,val,tr<<);

     else if(l>mid)

         change(l,r,val,tr<<|);

     else

         change(l,mid,val,tr<<),change(mid+,r,val,tr<<|);

     tree[tr].sum=tree[tr<<].sum+tree[tr<<|].sum;

 }

 inline long long query(int l,int r,int tr){//cout<<l<<" "<<r<<" "<<tree[tr].l<<" "<<tree[tr].r<<" "<<tr<<" ";

     if(tree[tr].l==l&&tree[tr].r==r)

         return tree[tr].sum;

     int mid=(tree[tr].l+tree[tr].r)>>;//cout<<mid<<endl;

     if(tree[tr].lazy)

         change(tree[tr].l,mid,tree[tr].lazy,tr<<),change(mid+,tree[tr].r,tree[tr].lazy,tr<<|),tree[tr].lazy=;

     if(r<=mid)

         return query(l,r,tr<<);

     else if(l>mid)

         return query(l,r,tr<<|);

     else

         return query(l,mid,tr<<)+query(mid+,r,tr<<|);

 }

 inline void solve(int L,int R,int l,int r){//cout<<L<<" "<<R<<" "<<l<<" "<<r<<endl;

     if(L>R)

         return;

     if(l==r){

         for(int i=L;i<=R;i++)

             if(q[i].flag==)

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

         return;

     }

     int mid=(l+r)>>,l1=,l2=;

     for(int i=L;i<=R;i++){//cout<<i<<endl;

         if(q[i].flag==){//cout<<"***"<<endl;

             if(q[i].k<=mid)

                 change(q[i].x,q[i].y,,),q1[l1++]=q[i];

             else

                 q2[l2++]=q[i];

         }

         else{//cout<<"&&&"<<endl;

             int lala=query(q[i].x,q[i].y,);//cout<<q[i].x<<" "<<q[i].y<<" "<<lala<<" "<<tree[1].sum<<endl;

             if(lala>=q[i].k)

                 q1[l1++]=q[i];

             else

                 q[i].k-=lala,q2[l2++]=q[i];

         }

     }//cout<<"lala"<<endl;

     for(int i=;i<l1;i++)

         if(q1[i].flag==)

             change(q1[i].x,q1[i].y,-,);

 //  memcpy(q+L,q1,sizeof(q[0])*l1);

 //  memcpy(q+L+l1,q2,sizeof(q[0])*l2);

     for(int i=;i<l1;i++)

         q[L+i]=q1[i];

     for(int i=;i<l2;i++)

         q[L+l1+i]=q2[i];

     solve(L,L+l1-,l,mid),solve(L+l1,R,mid+,r);

 }

 signed main(void){

 //  freopen("sequence10.in","r",stdin);

 //  freopen("out.out","w",stdout);

     n=intread();m=intread();cnt=;

 //  scanf("%lld%lld",&n,&m);

     for(int i=,l,s,x,y;i<=m;i++){

         l=intread();

 //      scanf("%lld",&l);

         if(l==)

             q[i].x=intread(),q[i].y=intread(),q[i].k=longread(),q[i].k=n-q[i].k+,q[i].flag=;

         else

             q[i].x=intread(),q[i].y=intread(),q[i].k=longread(),q[i].id=++cnt,q[i].flag=;

     }build(,n,);solve(,m,,n);

     for(int i=;i<=cnt;i++)

         printf("%lld\n",n-ans[i]+);

     return ;

 }//Cap ou pas cap. Cap.

BZOJ 2527: [Poi2011]Meteors

时空隧道

还是板子题...感觉我要废了TAT...

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 //by NeighThorn

 using namespace std;

 const int maxn=+;

 int n,m,k,cnt,ans[maxn],need[maxn];

 vector<int> v[maxn];

 unsigned long long tr[maxn];

 struct M{

     int x,y,k,id,flag;

 }q[maxn<<],q1[maxn<<],q2[maxn<<];

 inline void insert(int x,int y){

     for(;x<=m;x+=x&(-x))

         tr[x]+=y;

 }

 inline unsigned long long query(int x){

     unsigned long long res=;

     for(;x;x-=x&(-x))

         res+=tr[x];

     return res;

 }

 inline void solve(int L,int R,int l,int r){

     if(L>R)

         return;

     if(l==r){

         for(int i=L;i<=R;i++)

             if(q[i].flag==)

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

         return;

     }

     int mid=(l+r)>>,l1=,l2=;

     for(int i=L;i<=R;i++){

         if(q[i].flag==){

             if(q[i].id<=mid)

                 insert(q[i].x,q[i].k),insert(q[i].y+,-q[i].k),q1[l1++]=q[i];

             else

                 q2[l2++]=q[i];

         }

         else{

             unsigned long long lala=;

             for(int j=;j<v[q[i].id].size();j++)

                 lala+=query(v[q[i].id][j]);

             if(lala>=q[i].k)

                 q1[l1++]=q[i];

             else

                 q[i].k-=lala,q2[l2++]=q[i];

         }

     }

     for(int i=;i<l1;i++)

         if(q1[i].flag==)

             insert(q1[i].x,-q1[i].k),insert(q1[i].y+,q1[i].k);

     for(int i=;i<l1;i++)

         q[L+i]=q1[i];

     for(int i=;i<l2;i++)

         q[L+l1+i]=q2[i];

     solve(L,L+l1-,l,mid),solve(L+l1,R,mid+,r);

 }

 signed main(void){

     scanf("%d%d",&n,&m);

     for(int i=,x;i<=m;i++)

         scanf("%d",&x),v[x].push_back(i);

     for(int i=;i<=n;i++)

         scanf("%d",&need[i]);

     scanf("%d",&k);

     for(int i=,s,x,y;i<=k;i++){

         scanf("%d%d%d",&x,&y,&s);

         if(x<=y)

             q[++cnt].x=x,q[cnt].y=y,q[cnt].k=s,q[cnt].flag=,q[cnt].id=i;

         else

             q[++cnt].x=x,q[cnt].y=m,q[cnt].k=s,q[cnt].flag=,q[cnt].id=i,

             q[++cnt].x=,q[cnt].y=y,q[cnt].k=s,q[cnt].flag=,q[cnt].id=i;

     }

     for(int i=;i<=n;i++)

         q[++cnt].k=need[i],q[cnt].id=i,q[cnt].flag=;

     solve(,cnt,,k+);

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

         if(ans[i]==k+)

             puts("NIE");

         else

             printf("%d\n",ans[i]);

     }

     return ;

 }//Cap ou pas cap. Cap.

By NeighThorn

相关文章