精华内容
下载资源
问答
  • 线段树维护区间取min求和求max 维护最小值以及个数,次小值 标记清除时,分情况讨论 当lazy>max1 退出 当max1>lazy>max2(注意不要有等号) 更新 否则递归处理 据吉如一的论文上说是nlogn的复杂度...

    题解:

    线段树维护区间取min求和求max

    维护最小值以及个数,次小值

    标记清除时,分情况讨论

    当lazy>max1 退出

    当max1>lazy>max2(注意不要有等号) 更新

    否则递归处理

    据吉如一的论文上说是nlogn的复杂度(至今不知论文在何处)

    卡常?? 不懂常熟技巧 那就开个o2水一下。。。。

    这数的大小 正好2^31 刚开始没看。。对拍挺对交上去wa了

    #pragma G++ optimize (2)
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define N 1100000
    #define INF 2147483647
    #define il inline
    struct re{
      int max1,max2,num,h,t,lazy;
      ll sum;
    }p[N*4];
    ll b[N];
    int T,n,m;
    il void updata(int x)
    {
      p[x].sum=p[x*2].sum+p[x*2+1].sum;
      p[x].max1=max(p[x*2].max1,p[x*2+1].max1);
      if (p[x*2].max1==p[x*2+1].max1)
      {
        p[x].num=p[x*2].num+p[x*2+1].num;
        p[x].max2=max(p[x*2].max2,p[x*2+1].max2);
      } else
      {
        re xx=p[x*2],yy=p[x*2+1];
        if (xx.max1<yy.max1) swap(xx,yy);
        p[x].num=xx.num;
        p[x].max2=max(xx.max2,yy.max1); 
      } 
    }
    #define mid (h+t)/2
    void build(int x,int h,int t)
    {
      p[x].h=h; p[x].t=t; p[x].lazy=INF;
      if (h==t)
      { 
        p[x].max1=b[h],p[x].max2=-INF,p[x].num=1;
        p[x].sum=b[h];
        return;
      }
      build(x*2,h,mid); build(x*2+1,mid+1,t);
      updata(x);
    }
    void down(int x)
    {
      if (p[x].max1<=p[x].lazy) p[x].lazy=INF;
      if (p[x].lazy==INF) return;
      if (p[x].h!=p[x].t)
      {
        if (p[x].lazy<p[x*2].lazy) p[x*2].lazy=p[x].lazy;
        if (p[x].lazy<p[x*2+1].lazy) p[x*2+1].lazy=p[x].lazy;    
      } 
      if (p[x].max1>p[x].lazy&&p[x].max2<p[x].lazy)
      {
        p[x].sum=p[x].sum-1ll*(p[x].max1-p[x].lazy)*p[x].num;
        p[x].max1=p[x].lazy;
      } else
      {
        down(x*2); down(x*2+1);
        updata(x);
      }
      p[x].lazy=INF;
    }
    void change(int x,int h,int t,int w)
    {
      down(x);
      if (p[x].h>t||p[x].t<h) return;
      if (h<=p[x].h&&p[x].t<=t)
      {
        p[x].lazy=min(p[x].lazy,w); down(x); return;
      }
      change(x*2,h,t,w); change(x*2+1,h,t,w);
      updata(x);
    }
    int query1(int x,int h,int t)
    {
      down(x);
      if (p[x].h>t||p[x].t<h) return(-INF);
      if (h<=p[x].h&&p[x].t<=t) return(p[x].max1);
      return(max(query1(x*2,h,t),query1(x*2+1,h,t)));
    }
    ll query2(int x,int h,int t)
    {
      down(x);
      if (p[x].h>t||p[x].t<h) return(0);
      if (h<=p[x].h&&p[x].t<=t) return(p[x].sum);
      return(query2(x*2,h,t)+query2(x*2+1,h,t));
    }
    int main()
    {
      freopen("noip.in","r",stdin);
      freopen("noip.out","w",stdout);
      std::ios::sync_with_stdio(false);
      cin>>T;
      for (int ttt=1;ttt<=T;ttt++)
      {
       // clear();
        cin>>n>>m;
        for (int i=1;i<=n;i++) cin>>b[i];
        build(1,1,n);
        for (int i=1;i<=m;i++)
        {
          int x,y,z,w;
          cin>>x;
          if (x==0)
          {
            cin>>y>>z>>w;
            change(1,y,z,w);
          }
          if (x==1)
          {
            cin>>y>>z;
            cout<<query1(1,y,z)<<endl;
          }
          if (x==2)
          {
            cin>>y>>z;
            cout<<query2(1,y,z)<<endl;
          }
        }
      }
      return 0;
    }

     

    转载于:https://www.cnblogs.com/yinwuxiao/p/8784366.html

    展开全文
  • 0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value. 1 x y: Print the maximum value of ai that x≤i≤y. 2 x y: Print the sum of ai that x≤i≤y. Input The first ...

    题目链接

    hdu 5306

    题目描述

    Problem Description

    There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.

    0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value.
    1 x y: Print the maximum value of ai that x≤i≤y.
    2 x y: Print the sum of ai that x≤i≤y.

    Input

    The first line of the input is a single integer T, indicating the number of testcases.

    The first line contains two integers n and m denoting the length of the sequence and the number of operations.

    The second line contains n separated integers a1,…,an (∀1≤i≤n,0≤ai<231).

    Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).

    It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000.

    Output

    For every operation of type 1 or 2, print one line containing the answer to the corresponding query.

    Sample Input

    1
    5 5
    1 2 3 4 5
    1 1 5
    2 1 5
    0 3 5 3
    1 1 5
    2 1 5

    Sample Output

    5
    15
    3
    12

    题解

    吉如一的集训队论文讲得很清楚。存个模板。


    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    #include<vector>
    using namespace std;
    
    const int N=1000010;
    struct node{
        int mx,mx1,l,r,cnt;
        long long sum;
        void sol(int x){
            if(x>=mx) return;
            sum-=(mx-x)*1ll*cnt;
            mx=x;
        }
    }t[N*4];
    int a[N],op,x,y,z,n,m,T;
    
    void push_up(int k){
        t[k].cnt=0;
        t[k].sum=t[k*2].sum+t[k*2+1].sum;
        t[k].mx=max(t[k*2].mx,t[k*2+1].mx);
        t[k].mx1=max(t[k*2].mx1,t[k*2+1].mx1);
        if(t[k*2].mx==t[k].mx) t[k].cnt+=t[k*2].cnt;
        else t[k].mx1=max(t[k].mx1,t[k*2].mx);
        if(t[k*2+1].mx==t[k].mx) t[k].cnt+=t[k*2+1].cnt;
        else t[k].mx1=max(t[k].mx1,t[k*2+1].mx);
    }
    void push_down(int k){
        t[k*2].sol(t[k].mx);
        t[k*2+1].sol(t[k].mx);
    }
    void built(int k,int l,int r){
        t[k].l=l; t[k].r=r;
        if(l==r){
            t[k].mx=t[k].sum=a[l]; 
            t[k].mx1=-1; t[k].cnt=1;
            return;
        }
        int mid=(l+r)>>1;
        built(k*2,l,mid);
        built(k*2+1,mid+1,r);
        push_up(k);
    }
    void modify(int k,int l,int r,int x){
        if(t[k].mx<=x) return;
        if(t[k].l==l&&t[k].r==r&&t[k].mx1<x){
            t[k].sol(x);
            return;
        }
        push_down(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(l<=mid) modify(k*2,l,min(r,mid),x);
        if(r>mid) modify(k*2+1,max(l,mid+1),r,x);
        push_up(k);
    }
    int getmax(int k,int l,int r){
        if(t[k].l==l&&t[k].r==r) return t[k].mx;
        push_down(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(r<=mid) return getmax(k*2,l,r);
        else if(l>mid) return getmax(k*2+1,l,r);
        return max(getmax(k*2,l,mid),getmax(k*2+1,mid+1,r));
    }
    long long getsum(int k,int l,int r){
        if(t[k].l==l&&t[k].r==r) return t[k].sum;
        push_down(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(r<=mid) return getsum(k*2,l,r);
        else if(l>mid) return getsum(k*2+1,l,r);
        return getsum(k*2,l,mid)+getsum(k*2+1,mid+1,r);
    }
    int main(){
        scanf("%d",&T);
        while(T--){
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) scanf("%d",a+i);
            built(1,1,n);
            for(int i=1;i<=m;i++){
                scanf("%d%d%d",&op,&x,&y);
                if(op==0) {
                    scanf("%d",&z);
                    modify(1,x,y,z);
                }
                else if(op==1) printf("%d\n",getmax(1,x,y));
                else printf("%lld\n",getsum(1,x,y));
            }
        }
        return 0;
    }
    展开全文
  • 设势函数=每个点所管区间内互异值的个数总和 一开始势能最大nlogn 操作1使得势能最多增加logn 操作2我们这样处理:每个点记录一下最大值和次大值,若x大于最大值退掉,若x在最大值与次大值之间则打一个tag,若x...

    这里写图片描述

    比如这题
    设势函数=每个点所管区间内互异值的个数总和
    一开始势能最大nlogn
    操作1使得势能最多增加logn
    操作2我们这样处理:每个点记录一下最大值和次大值,若x大于最大值退掉,若x在最大值与次大值之间则打一个tag,若x小于次大值则递归下去。
    可以发现,每次递归下去时势函数都至少减1,这时我们要花费向下走左右子树,共2的时间。

    那么,总的时间复杂度就控制在了势函数最大值(n+m) log n上。
    但是题解的分析是n log^2 n的,不知道这个奇妙的分析方法有没有问题。

    2019 UPD

    这种线段树叫吉司机线段树。
    复杂度的确是O((n+m)logn)O((n + m) log n)O((n+m)logn)
    假如有区间加操作,那么复杂度可以证明为O(nlog2n)O(n log^2 n)O(nlog2n)
    但是实践上效率更接近于O(nlogn)O(n log n)O(nlogn),并没有能卡成log^2的数据(没准他本来就是一个log呢?)

    展开全文
  • 0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value. 1 x y: Print the maximum value of ai that x≤i≤y. 2 x y: Print the sum of ai that x≤i≤y. Input The first ...

    Problem Description
    There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.

    0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value.
    1 x y: Print the maximum value of ai that x≤i≤y.
    2 x y: Print the sum of ai that x≤i≤y.

    Input
    The first line of the input is a single integer T, indicating the number of testcases.

    The first line contains two integers n and m denoting the length of the sequence and the number of operations.

    The second line contains n separated integers a1,…,an (∀1≤i≤n,0≤ai<231).

    Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).

    It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000.

    Output
    For every operation of type 1 or 2, print one line containing the answer to the corresponding query.

    Sample Input
    1
    5 5
    1 2 3 4 5
    1 1 5
    2 1 5
    0 3 5 3
    1 1 5
    2 1 5

    Sample Output
    5
    15
    3
    12

    解题报告

    我们对于线段树的每个结点,维护最大值max,最大值出现次数cnt,严格次大值sec和区间和sum。

    修改时,对于可修改结点k,若

    1. t≥max(k):修改对于该区间无效,返回。

    2. sec(k) < t < max(k):t只对max(k)发生影响,令max(k)=t并更新区间和,返回。

    3. sec(k) ≤ t:无法简单地更新区间和了……

    复杂度是 (mlog n),证明的话可以参看16年集训队吉爷的论文

    这个题要优化输入输出,否则可能超时

    原题链接

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define MAX_N 1000005
    using namespace std;
    typedef long long LL;
    
    const int MAXS = 40*1024*1024;
    char buf[MAXS],bufout[MAXS],*ch,*chout;
    
    void read(int &x){
        for(++ch;*ch<=32;++ch);
        for(x=0;*ch>='0';++ch) x=x*10+*ch-'0';
    }
    
    void out(int x){
        if(!x) *(++chout)='0';
        else{
            char *ch0=chout,*ch1=chout+1;
            while(x){
                *(++ch0)=x%10+'0';
                x/=10;
            }
            chout=ch0;
            while(ch1<=ch0) swap(*(ch1++),*(ch0--));
        }
        *(++chout)='\n';
    }
    
    void out(long long x){
        if(!x) *(++chout)='0';
        else{
            char *ch0=chout,*ch1=chout+1;
            while(x){
                *(++ch0)=x%10+'0';
                x/=10;
            }
            chout=ch0;
            while(ch1<=ch0) swap(*(ch1++),*(ch0--));
        }
        *(++chout)='\n';
    }
    
    void std_init(){
        ch=buf-1;
        chout=bufout-1;
        fread(buf,1,MAXS,stdin);
    }
    
    void std_out(){
        fwrite(bufout,1,chout-bufout+1,stdout);
    }
    
    /*---------------------------------------------------------------*/
    
    struct node{LL sum;int _max,sa,cum;};//和 最大值 次大值 最大值数量
    
    node dat[MAX_N*2+100];
    int res[MAX_N];
    
    void maintain(int k){
        int tmpk=k<<1;
        dat[k].sum=dat[tmpk].sum+dat[tmpk|1].sum;
        dat[k].sa=max(dat[tmpk].sa,dat[tmpk|1].sa);
        if(dat[tmpk]._max>dat[tmpk|1]._max){
            dat[k]._max=dat[tmpk]._max;
            dat[k].cum=dat[tmpk].cum;
            if(dat[tmpk|1]._max>dat[k].sa) dat[k].sa=dat[tmpk|1]._max;
        }else if(dat[tmpk]._max<dat[tmpk|1]._max){
            dat[k]._max=dat[tmpk|1]._max;
            dat[k].cum=dat[tmpk|1].cum;
            if(dat[tmpk]._max>dat[k].sa) dat[k].sa=dat[tmpk]._max;
        }else{
            dat[k]._max=dat[tmpk]._max;
            dat[k].cum=dat[tmpk].cum+dat[tmpk|1].cum;
        }
    }
    
    void dec(int k,int t){
        if(t>=dat[k]._max) return ;
        dat[k].sum-=1LL*(dat[k]._max-t)*dat[k].cum;
        dat[k]._max=t;
    }
    
    void pushdown(int k){
        dec(k<<1,dat[k]._max);
        dec(k<<1|1,dat[k]._max);
    }
    
    void build(int k,int l,int r){
        if(l==r) dat[k].sum=dat[k]._max=res[l],dat[k].cum=1,dat[k].sa=-1;
        else{
            int mid=r+l>>1,tmpk=2*k;
            build(tmpk,l,mid);
            build(tmpk+1,mid+1,r);
            maintain(k);
        }
    }
    
    void change(int k,int l,int r,int ql,int qr,int t){
        if(l>qr||r<ql||dat[k]._max<=t) return ;
        if(r<=qr&&l>=ql&&t>dat[k].sa){
            dec(k,t); return ;
        }
        pushdown(k);
        int mid=r+l>>1,tmpk=2*k;
        change(tmpk,l,mid,ql,qr,t);
        change(tmpk+1,mid+1,r,ql,qr,t);
        maintain(k);
    }
    
    int query1(int k,int l,int r,int ql,int qr){
        if(l>qr||r<ql) return 0;
        if(r<=qr&&l>=ql) return dat[k]._max;
        pushdown(k);
        int mid=l+r>>1,tmpk=2*k;
        return max(query1(tmpk,l,mid,ql,qr),query1(tmpk+1,mid+1,r,ql,qr));
    }
    
    LL query2(int k,int l,int r,int ql,int qr){
        if(l>qr||r<ql) return 0;
        if(r<=qr&&l>=ql) return dat[k].sum;
        pushdown(k);
        int mid=l+r>>1,tmpk=2*k;
        return query2(tmpk,l,mid,ql,qr)+query2(tmpk+1,mid+1,r,ql,qr);
    }
    
    int main()
    {
        std_init();
        int T;
        read(T);
        for(int t=1;t<=T;t++){
            int n,m;
            read(n);read(m);
            for(int i=1;i<=n;i++)
                read(res[i]);
            build(1,1,n);
            while(m--){
                int op,x,y;
                read(op);read(x);read(y);
                if(op) out(op==1?query1(1,1,n,x,y):query2(1,1,n,x,y));
                else{
                    int val;read(val);
                    change(1,1,n,x,y,val);
                }
            }
        }
        std_out();
        return 0;
    }
    展开全文
  • 以及点标为mx的边的和,如果当前点的id>=mx,显然不用更新,如果cx,那么直接将点标为mx的边改为id,并打上懒标记,如果id,则需要递归两个儿子,虽然需要递归两边,但是势能分析可知区间取min的复杂度是nlogn的:记...
  • 2)给出参数U,V,C,对于区间[U,V]里的每个数i,将a[i]赋值为max(a[i]+C,0)。 3)给出参数U,V,输出a[U],a[U+1],...,a[V-1],a[V]里值为0的数字个数。   Input 第一行包含两个正整数N,M(1,M),分别表示...
  • HDU5306 Gorgeous Sequence Problem Description There is a sequence a of length n. We use ai to denote the i-th element in this sequence....0 x y t: For every x≤i≤y, we use min(ai,t) to re
  • JAVA实现指定区间取N个不重复随机数

    千次阅读 2018-03-17 11:15:36
    近日在面试中多次被问到从规定区间取N个随机数的问题,所以今日将实现方式整理一下,代码如下: 传统双重循环去重的方式 /** * 功能:产生min-max中的n个不重复的随机数 * * min:产生随机数的其实位置 *...
  • iOS 取区间

    2017-03-01 16:15:00
    candleWidth = MIN(MAX(1, candleWidth),15); 1~15 转载于:https://www.cnblogs.com/zhangxiaozhe/p/6484786.html
  • 计算公式: Random rand = new Random(); int i = rand.nextInt(max-min+1)+min; i = rand.nextInt()*(max-min+1)+min; double j = rand.nextDouble()*(max-min+1)+min;
  • 题目链接:LOJ 题目大意:看到题目名字应该都知道是啥了吧。 ...(次数 $k=0$ 即可) 在这里再写一遍式子。(用久了应该要背了) $g(n,0)=n-1$ $g(n,j)=\begin{cases}g(n,j-1)&p_j^2&...
  • 尺法 和区间调度

    2016-12-22 00:18:38
    /*尺法 给定义一个数列 {An} 和整数S 求出总和不小于S的连续子序列长度的最小值 如果解不存在 输出0 EG:输入: N=5; S=15; A={5,1,3,5,10,7,4,9,2,8};...# define min(a,b)((a)<(b)?(a):(b)) # de
  • Math.random()一个区间的随机数

    千次阅读 2016-04-10 19:47:11
    Math.random()是[0,1)之间的随机数,包括0但是不包括1,,强转为int时,只到0,如果特定区间的随机数: int num=(int)(min+Math.random()*(max-min));包括min但是不包括max;例如1~11之间的随机数,即包括1...
  • 在闭区间[0, 1]内,我们随机取出两点(服从均匀分布)A和B,形成一个新的闭区间[min{A,B}, max{A,B}]。如此反复n次,我们就有了n个随机闭区间。那么这n个闭区间不出现重叠的概率是多大呢? 将问题可以简单转化为2n个...
  • ORACLE 连续值、时间段的区间

    千次阅读 2018-09-15 01:53:24
    连续值区间 --测试数据 CREATE TABLE Z_NUMS AS SELECT LEVEL AS NUM1 FROM DUAL CONNECT BY LEVEL &amp;amp;amp;lt;=1000; DELETE FROM Z_NUMS WHERE NUM1 LIKE '%7%'; COMMIT; SELECT MIN...
  • 分析:窝们需要找到最满足条件的k个区间 进行不断更新最大值; 首先由于原序列是递增的,因此维护一个优先队列,只需要将r小的放在前面即可; 由于优先队列已经存在了k个 因此窝们每次放进的当前...
  • 如果要min,max)之间的随机数,公式:Math.random()*(max-min) + min;这篇文章主要思考这个公式的由来。 换个角度思考: 已知0<y<1,y经过一系列运算后值变为z,z始终满足m<z<n,其中m,n为正整数,...
  • 1.如果考虑暴力的话,一种想法是枚举左端和右端要选取的区间(如果我们按长度排序的话),那么只要发现当前选取的这些从左到右的区间可以得到m及以上就可以了,没必要特地考虑具体选哪些,然后ans = min(ans, 右...
  • 题目 代码 #include&amp;amp;lt;algorithm&amp;amp;gt; #include&amp;amp;lt;cstdio&amp;amp;gt; using namespace std; int n,kk,t,a[2011],ans,answ,m...{ return min(x,
  • 算法标签:线段树区间取min
  • Description A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are ... Write a program to find the min...
  • 法一:#include &lt;bits/stdc++.h&gt; using namespace std; const int INF = 0x3f3f3f3f; const int N = 1e5 + 10;...int a_min[N][20]; int a[N]; int n; void Init() { for(int i = 1; i &lt;=...
  • 区间取min,区间求和。 N<=100000 要求O(nlogn)级别的算法 直观体会一下,区间取min,还要维护区间和 增加的长度很不好求。。。。 然鹅, 从前有一个来自杭州天水幼儿园的julao叫九条可怜 他发明了一...
  • 这两道题加上区间取min max应该算线段树几道比较不寻常的题目 其实也是挺好理解的 对于区间/d 显然在log次后就会等于0 而我们注意到如果区间中数都相等那么就可以一起除 也就是说每个区间需要log次除法能相等 ...
  • 2016集训队论文吉如一

    2018-09-04 21:45:00
    1.区间取min,区间查询最大值,区间求和 这个之前做过 记录区间最大值mx1,次大值mx2,最大值个数 插入的时候分情况讨论 if (mx1<x) 不做 if (max1>=x&&max2<x) 赋值max1 不然就递归下去 ...
  • bzoj4695: 最假女选手 给出长为N(≤5e5)的序列,要求支持区间加、区间取min/max、区间求和、区间求min/max。 我 好久好久以前 就想学这个科技… O(nlog^2n)的SegmentTreeBeats!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 411
精华内容 164
关键字:

区间取min