玲珑oj 1117 线段树+离线+离散化,laz大法

1117 - RE：从零开始的异世界生活

Time Limit：1s Memory Limit：256MByte

Submissions：438Solved：68

DESCRIPTION

486到了异世界，看到了一群可爱的妹子比如蕾姆啊，艾米莉亚啊，拉姆啊，白鲸啊，怠惰啊等等!
有一天膜女告诉486说她的能力可能不能再用了，因为膜女在思考一个数据结构题，没心情管486了。
486说我来帮你做，膜女说你很棒棒哦！

给一个集合，最开始为空（不是数学上的集合）
五个操作：

1、插入x
2、把小于x的数变成x
3、把大于x的数变成x
4、求集合中第x小数
5、求集合中小于x的数个数

INPUT

第一行一个数m
后面有m行，每行格式为opt x，opt表示是什么操作，x表示操作的值

OUTPUT

对于每个4,5操作，输出一个值表示答案

SAMPLE INPUT

5
1 1
1 3
4 1
2 33
4 1

SAMPLE OUTPUT

1
33

HINT

m <= 100000 , x <= 1000000000

SOLUTION

“玲珑杯”ACM比赛 Round #14

这个题目是暑假前玲珑的一次我参加的比赛，很遗憾当时还很弱不会ST直接放弃了，现在又回来看见，当时看别人博客题解是什么值域线段树，好吧我也不会，

copy一个代码跑了960+ms险过感觉怎么这么慢捏，再次看题目感觉就是普通线段树就可做。

虽然n<1e9,但m最大10w，最多也就10w个不同的x，我想到用map离散化处理一下，为了方便询问我是从2开始的，由于要对所有的x离散化，所以必须先离散化结束才能应对所有的询问，这里采用了离线的作法，先保存询问值，预处理完在依次模拟询问的过程。

没有很奇葩的询问，单点更新，区间修改和二分查找，注意细节的话就好了。

 #include<bits/stdc++.h>

 using namespace std;

 #define inf 0x3f3f3f3f

 #define LL long long

 #define MAX 100005

 map<int,int>M1;

 int N,x[MAX]={},P[MAX];

 struct Ask

 {

   int opt,x;

 }a[MAX];

 struct SegTree

 {

   #define M ((L+R)>>1)

   #define lc (id<<1)

   #define rc (id<<1|1)

   int sum[MAX<<],laz[MAX<<];//laz[i]表示全部变为i

   void init()

   {

       memset(sum,,sizeof(sum));

       memset(laz,-,sizeof(laz));

   }

   void pushup(int L,int R,int id)

   {

       sum[id]=sum[lc]+sum[rc];

   }

   void pushdown(int L,int R,int id)

   {

       if(laz[id]!=-){

         sum[lc]=sum[rc]=;

         laz[lc]=laz[rc]=;

         laz[id]=-;

       }

   }

   void irt(int L,int R,int id,int x,int v)

   {

       if(L==R){

         sum[id]+=v;

         return;

       }

       pushdown(L,R,id);

       if(x<=M) irt(L,M,lc,x,v);

       else     irt(M+,R,rc,x,v);

       pushup(L,R,id);

   }

   int change(int L,int R,int id,int l,int r)

   {

      if(L>=l&&R<=r){

         int res=sum[id];

         sum[id]=;

         laz[id]=;

         return res;

      }

      pushdown(L,R,id);

      int res=;

      if(l<=M) res+=change(L,M,lc,l,r);

      if(r>M)  res+=change(M+,R,rc,l,r);

      pushup(L,R,id);

      return res;

   }

   int ask1(int L,int R,int id,int x)

   {

       if(L==R) return P[L];

       pushdown(L,R,id);

       if(sum[lc]>=x){

         return ask1(L,M,lc,x);

       }

       else{

         return ask1(M+,R,rc,x-sum[lc]);

       }

   }

   int ask2(int L,int R,int id,int x)

   {

       if(L==R) return sum[id];

       pushdown(L,R,id);

       if(x<=M) return ask2(L,M,lc,x);

       else if (x>M) return sum[lc]+ask2(M+,R,rc,x);

   }

 }seg;

 int main()

 {

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

     int n,m,i,j,k;

     scanf("%d",&n); N=;

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

     {

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

         x[i]=a[i].x;

     }

     sort(x+,x+n+);

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

     {

        if(x[i]==x[i-]) continue;

        M1[x[i]]=++N;

        P[N]=x[i];

     }

     N++;

     seg.init();

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

     {

         int x1=M1[a[i].x];

         if(a[i].opt==){

             seg.irt(,N,,x1,);

         }

         else if(a[i].opt==){

             seg.irt(,N,,x1,seg.change(,N,,,x1-));

         }

         else if(a[i].opt==){

             seg.irt(,N,,x1,seg.change(,N,,x1+,N));

         }

         else if(a[i].opt==){

             printf("%d\n",seg.ask1(,N,,a[i].x));

         }

         else if(a[i].opt==){

             printf("%d\n",seg.ask2(,N,,x1-));

         }

     }

     return ;

 }

巴特西

玲珑oj 1117 线段树+离线+离散化,laz大法

最新文章

热门文章