over 3 years ago

题如其名。

本来写的线段树套平衡树。但是200+行实在不想调。

就尝试了人生中第一次分块。

WA的要死了==对排的也要哭了==

所以……总结一下分块搞错的地方……

room=(int)sqrt(n);

1、会分成n/room+1块。在一开始排序的时候注意块数。

2、第pos个点所在块为(pos+room-1)/room

3、注意二分!mid=(left+right+1)则后文left=mid;

4、分块后的查询要注意左右端点可能在同一块。

5、在修改时要注意position[]作为原数组的位置映射到排序后位置的数组要一并修改。minn,maxx,num由于原数组修改也要修改。

/**************************************************************
    Problem: 3196
    User: LaVenDer
    Language: C++
    Result: Accepted
    Time:4708 ms
    Memory:1760 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define maxn 60001
#define inf 1000000000
using namespace std;
struct point
{
    int num,pos;
}a[maxn]={0};
int num[maxn]={0},position[maxn]={0};
int n,m,border,tot=0,minn=inf,maxx=-inf,room;
int calcleft(int x)
{
    return (x-1)*room+1;
}
int calcright(int x)
{
    return x*room;
}
int  readln()
{
    char c;int result=0,bj=1;
    c=getchar();
    while (c!='-'&&!(c>='0'&&c<='9')) c=getchar();
    if (c=='-') {bj=-1;c=getchar();}
    while  (c<='9'&&c>='0')
    {
        result=result*10+c-'0';
        c=getchar();
    }
    return result*bj;
}
int cmp(const point x,const point y)
{
    return x.num<y.num;
}
void prepare()
{
    room=(int)floor(sqrt(n));
    for (int i=1;i<=n/room;i++)
    {
        sort(a+calcleft(i),a+calcright(i)+1,cmp);
    }
    int k=calcleft(n/room+1);
    if (k<=n)sort(a+k,a+1+n,cmp);
}
int find(int left,int right,int k)
{
    int mid,l=left,r=right;
    if (a[left].num>=k) return 0;
    if (a[right].num<k) return (right-left+1);
    while (l<r)
    {
        mid=(l+r+1)>>1;
        if (a[mid].num>=k) r=mid-1;
        else l=mid;
    }
    return l-left+1;
}
int besure(int x)
{
    return (x+room-1)/room;
}
int queryrank(int l,int r,int k)
{
    int result=0,i,left=besure(l),right=besure(r);
    if (left==right)
    {
        for (i=l;i<=r;i++) if (num[i]<k) result++;
    return result;
    }
    for (i=l;i<=left*room;i++)
        if (num[i]<k) result++;
    for (i=(right-1)*room+1;i<=r;i++)
      if (num[i]<k) result++;
    for (i=left+1;i<=right-1;i++)
    {
        result+=find(calcleft(i),calcright(i),k);
    }
    return result;
}
int binary(int left,int right,int k)
{
    int l,r,mid,p;
    l=minn;r=maxx;
    while (l<r)
    {
        mid=(l+r+1)>>1;
        p=queryrank(left,right,mid)+1;
        if (p>k) r=mid-1;
        else l=mid;
    }
    return r;
}
void change(int pos,int x)
{
    int i,k,til,record=position[pos];
    if (x>maxx) maxx=x;
    if (x<minn) minn=x;
    num[pos]=x;
    if (x>a[record].num)
    {
        til=record+1;int border=calcright(besure(pos));
        while (til<=border&&a[til].num<x) til++;
        til--;
        for (i=record;i<=til-1;i++)
        {
            a[i].pos=a[i+1].pos,a[i].num=a[i+1].num;
            position[a[i].pos]=i;
        }  
        a[til].pos=pos;a[til].num=x;position[a[til].pos]=til;
    }
    if (x<a[record].num)
    {
        til=record-1;int border=calcleft(besure(pos));
        while (til>=border&&a[til].num>x) til--;
        til++;
        for (i=record;i>=til+1;i--)
        {
            a[i].pos=a[i-1].pos;a[i].num=a[i-1].num;position[a[i].pos]=i;}
        a[til].pos=pos;a[til].num=x;position[a[til].pos]=til;
    }
}
int findpre(int left,int right,int k)
{
     int mid;
     while (left<right)
     {
        mid=(left+right+1)>>1;
        if (a[mid].num<k) left=mid;
        else right=mid-1;
     }
     return a[left].num;
}
int querypre(int l,int r,int k)
{
    int i,temp,pre=-inf;
    int left=besure(l),right=besure(r);
    if (left==right)
    {
        for (i=l;i<=r;i++) if (num[i]>pre&&num[i]<k) pre=num[i];
        return pre;
    }
    for (i=l;i<=left*room;i++)
      if (num[i]>pre&&num[i]<k) pre=num[i];
    for (i=(right-1)*room+1;i<=r;i++)
      if (num[i]>pre&&num[i]<k) pre=num[i];
    for (i=left+1;i<=right-1;i++)
    {
        temp=findpre(calcleft(i),calcright(i),k);
        if (temp>pre&&temp<k) pre=temp;
    }  
    return pre; 
}
int findsuc(int left,int right,int k)
{
     int mid;
     while (left<right)
     {
        mid=(left+right)>>1;
        if (a[mid].num>k) right=mid;
        else left=mid+1;
     }
     return a[left].num;
}
int querysuc(int l,int r,int k)
{   int i,j,temp,suc=inf;
    int left=besure(l),right=besure(r);
    if (left==right)
    {
        for (i=l;i<=r;i++) if (num[i]<suc&&num[i]>k) suc=num[i];
        return suc;
    }
    for (i=l;i<=left*room;i++)
      if (num[i]<suc&&num[i]>k) suc=num[i];
    for (i=(right-1)*room+1;i<=r;i++)
      if (num[i]<suc&&num[i]>k) suc=num[i];
    for (i=left+1;i<=right-1;i++)
    {
        temp=findsuc(calcleft(i),calcright(i),k);
        if (temp<suc&&temp>k) suc=temp;
    }
    return suc;
}
int main()
{
    int i,l,opt,r,x,y,k;
    n=readln();m=readln();
    for (i=1;i<=n;i++)
    {
        a[i].num=readln();a[i].pos=i;
        if (a[i].num>maxx) maxx=a[i].num;
        if (a[i].num<minn) minn=a[i].num;
        num[i]=a[i].num;
    }
    prepare();
    for (i=1;i<=n;i++)  position[a[i].pos]=i;
    for (i=1;i<=m;i++)
    {
        opt=readln();
        if (opt==1) {l=readln();r=readln();k=readln();printf("%d\n",queryrank(l,r,k)+1);    }
        if (opt==2) {l=readln();r=readln();k=readln();if (k>r-l+1) printf("wrong");else printf("%d\n",binary(l,r,k));    }  
        if (opt==3) {x=readln();y=readln();change(x,y);  }
        if (opt==4) {l=readln();r=readln();k=readln();printf("%d\n",querypre(l,r,k)); }
        if (opt==5) {l=readln();r=readln();k=readln();printf("%d\n",querysuc(l,r,k));}
    }
}
← 【bzoj1010】【dp】【斜率优化】玩具装箱 【bzoj1007】【平几?】水平可见直线 →
 
comments powered by Disqus