HDU5828 Rikka with Sequence 线段树

分析：这个题和bc round 73应该是差不多的题，当时是zimpha巨出的，那个是取phi，这个是开根

吐槽：赛场上写的时候直接维护数值相同的区间，然后1A，结果赛后糖教一组数据给hack了，仰慕

由于是开根，所以存在两个数刚开始差为1，加上某数再开根依旧是差1，这样维护相同数区间的就没用了

比如(2,3) +6-->(8,9)开根-->(2,3)如果全是这样的操作，即使维护相同的数，每次开根的复杂度都是O(N),不T才怪

这样只需要维护区间最大值最小值，当差1的时候，看看是否开根后还是差1，这样就可以变开根为减了

加强数据后，1591ms。。。（还是太年轻）

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <stdlib.h>

using namespace std;

typedef long long LL;

const int BufferSize=<<;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

    if(head==tail) {

        int l=fread(buffer,,BufferSize,stdin);

        tail=(head=buffer)+l;

    }

    return *head++;

}

inline int read() {

    int x=,f=;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=Getchar()) x=x*+c-'';

    return x*f;

}

const int N=1e5+;

LL sum[N<<],lz[N<<],mx[N<<],mn[N<<];

void up(int rt){

  sum[rt]=sum[rt<<]+sum[rt<<|];

  mx[rt]=max(mx[rt<<],mx[rt<<|]);

  mn[rt]=min(mn[rt<<],mn[rt<<|]);

}

void build(int rt,int l,int r){

  lz[rt]=;

  if(l==r){sum[rt]=read();mn[rt]=mx[rt]=sum[rt];return;}

  int mid=l+r>>;

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

  up(rt);

}

void down(int rt,int l,int r){

  if(lz[rt]!=){

    int mid=l+r>>;

    lz[rt<<]+=lz[rt];

    lz[rt<<|]+=lz[rt];

    mn[rt<<]+=lz[rt];

    mx[rt<<]+=lz[rt];

    mx[rt<<|]+=lz[rt];

    mn[rt<<|]+=lz[rt];

    sum[rt<<]+=lz[rt]*(mid-l+);

    sum[rt<<|]+=lz[rt]*(r-mid);

    lz[rt]=;

  }

}

int x,y,t,T,n,m;

void kaigen(int rt,int l,int r){

  if(x<=l&&r<=y){

     if(mx[rt]==mn[rt]){

        lz[rt]-=mx[rt];

        mx[rt]=sqrt(mx[rt]);

        mn[rt]=mx[rt];

        lz[rt]+=mx[rt];

        sum[rt]=mx[rt]*(r-l+);

        return;

     }

     else if(mx[rt]==mn[rt]+){

       LL x1=sqrt(mx[rt]);

       LL x2=sqrt(mn[rt]);

       if(x1==x2+){

          lz[rt]-=(mx[rt]-x1);

          sum[rt]-=(mx[rt]-x1)*(r-l+);

          mx[rt]=x1;mn[rt]=x2;

          return;

       }

    }

  }

  int mid=l+r>>;down(rt,l,r);

  if(x<=mid)kaigen(rt<<,l,mid);

  if(y>mid)kaigen(rt<<|,mid+,r);

  up(rt);

}

void add(int rt,int l,int r){

  if(x<=l&&r<=y){

    lz[rt]+=t;

    sum[rt]+=1ll*(r-l+)*t;

    mx[rt]+=t;mn[rt]+=t;

    return ;

  }

  int mid=l+r>>;down(rt,l,r);

  if(x<=mid)add(rt<<,l,mid);

  if(y>mid)add(rt<<|,mid+,r);

  up(rt);

}

LL get(int rt,int l,int r){

  if(x<=l&&r<=y)return sum[rt];

  int mid=l+r>>;down(rt,l,r);

  LL ret=;

  if(x<=mid)ret+=get(rt<<,l,mid);

  if(y>mid)ret+=get(rt<<|,mid+,r);

  return ret;

}

int main(){

  T=read();

  while(T--){

    n=read();m=read();

    build(,,n);

    while(m--){

      int op;

      op=read();x=read();y=read();

      if(op==){

        t=read();add(,,n);

      }

      else if(op==)kaigen(,,n);

      else printf("%I64d\n",get(,,n));

    }

  }

  return ;

}

巴特西

HDU5828 Rikka with Sequence 线段树

最新文章

热门文章