精华内容
下载资源
问答
  • 【链接】 ... 【题意】 给你n个数,m个操作。 操作有两种: ...1.U x y 将数组第x位变为y  ...2. Q x y 问数组第x位...线段树维护信息:区间最长连续上升序列,前缀最长上升序列,后缀最长上升序列。 pushup(p)修改的时...

    【链接】

    http://acm.hdu.edu.cn/showproblem.php?pid=3308

    【题意】

    给你n个数,m个操作。

    操作有两种:

    1.U x y 将数组第x位变为y  

    2. Q x y 问数组第x位到第y位连续最长子序列的长度

    【思路】

    满足区间可加。

    线段树维护信息:区间最长连续上升序列,前缀最长上升序列,后缀最长上升序列。

    pushup(p)修改的时候注意判断条件

    【代码】

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6 + 6;
    int a[maxn];
    
    struct node {
    	int l, r, sub, lc, rc;
    }t[maxn<<2];
    
    inline void pushup(int p) {//本题核心,pushup的修改
    	int mid = (t[p].l + t[p].r )>> 1;
    	t[p].lc = t[p << 1].lc; t[p].rc = t[p << 1 | 1].rc;
    	t[p].sub = max(t[p << 1].sub, t[p << 1 | 1].sub);
    	if (a[mid] < a[mid + 1]) {
    		if (t[p].lc == mid - t[p].l + 1)t[p].lc += t[p << 1 | 1].lc;
    		if (t[p].rc == t[p].r - mid)t[p].rc += t[p << 1].rc;
    		t[p].sub = max(t[p << 1].rc + t[p << 1 | 1].lc, t[p].sub);
    	}
    }
    
    void build(int p, int l, int r) {
    	t[p].l = l; t[p].r = r;
    	if (l == r) { t[p].lc = t[p].rc = t[p].sub = 1; return; }
    	int mid =( l + r )>> 1;
    	build(p << 1, l, mid);
    	build(p << 1 | 1, mid + 1, r);
    	pushup(p);
    }
    
    void update(int p, int pos, int v) {//单点修改
    	if (t[p].l == t[p].r) {
    		return;
    	}
    	int mid = (t[p].l + t[p].r) >> 1;
    	if (pos <= mid)update(p << 1, pos, v);
    	else update(p << 1 | 1, pos, v);
    	pushup(p);
    }
    
    int query(int p, int l, int r) {//查询区间[t[p].l,t[p],r]的最长连续上升子序列,核心
    	if (l <= t[p].l&&r >= t[p].r) {
    		return t[p].sub;
    	}
    	int mid = (t[p].l + t[p].r) >> 1;
    	if (r <= mid)return query(p << 1, l, r);
    	if (l > mid)return query(p << 1 | 1, l, r);//一共三种可能:左区间,右区间或者横跨左右两个区间
    	int t1 = query(p << 1, l, r);
    	int t2 = query(p << 1 | 1, l, r);
    	int ans = max(t1, t2);
    	if (a[mid] < a[mid + 1]) {
    		ans = max(ans, min(t[p << 1].rc,mid-l+1) + min(t[p << 1 | 1].lc,r-mid));
    	}
    	return ans;
    }
    
    int main() {
    	int T;scanf("%d", &T); 
    	while (T--) {
    		int n, m;
    		scanf("%d%d", &n, &m);
    		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    		build(1, 1, n);
    		while (m--) {
    			char op[5];
    			int x, y;
    			scanf("%s%d%d", op, &x, &y);x++;
    			if (op[0] == 'U') {
    				a[x] = y;
    				update(1, x, y);
    			}
    			else {
    				y++;
    				printf("%d\n", query(1, x, y));
    			}
    		}
    	}
    	scanf("%d", &T);
    }

     

    展开全文
  • 询问区间内最大的LCIS 我们需要记录包含最左点的LCIS ,包含最右点的LCIS,和这段的最长LCIS,然后向上更新就没了! #include #include #include #include #include #include #include #include #include #...
    询问区间内最大的LCIS  
    我们需要记录包含最左点的LCIS ,包含最右点的LCIS,和这段的最长LCIS,然后向上更新就没了!

    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<queue>
    #include<vector>
    #include<iostream>
    #include<string>
    #include<set>
    #include<map>
    #include<algorithm>
    using namespace std;
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    #define nn 100010
    #define LL long long
    #define ULL unsiged long long
    #define mod 0x7fffffff
    #define inf oxfffffffffff
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    int a[nn];
    struct node
    {
        int ln,rn,len;
    }tree[nn<<2];
    void pushup(int l,int r,int rt)
    {
        int mid=(l+r)>>1;
        tree[rt].len=max(tree[rt<<1].len,tree[rt<<1|1].len);
        tree[rt].ln=tree[rt<<1].ln;
        tree[rt].rn=tree[rt<<1|1].rn;
        if(a[mid]<a[mid+1])
        {
            if(tree[rt].ln==(mid-l+1))
                tree[rt].ln+=tree[rt<<1|1].ln;
            if(tree[rt].rn==(r-mid))
                tree[rt].rn+=tree[rt<<1].rn;
            tree[rt].len=max(tree[rt].len,tree[rt<<1].rn+tree[rt<<1|1].ln);
        }
        //tree[rt].len=max(tree[rt].len,max(tree[rt].ln,tree[rt].rn));
    }
    void build(int l,int r,int rt)
    {
        if(l==r)
        {
            tree[rt].ln=1;
            tree[rt].len=1;
            tree[rt].rn=1;
            return;//你妹的
        }
        int mid=(l+r)>>1;
        build(lson);
        build(rson);
        pushup(l,r,rt);
    }
    void updata(int ll,int v,int l,int r,int rt)
    {
        if(l==r)
        {
            a[ll]=v;
            return;
        }
        int mid=(l+r)>>1;
        if(ll<=mid)
            updata(ll,v,lson);
        else updata(ll,v,rson);
        pushup(l,r,rt);
    }
    int query(int ll,int rr,int l,int r,int rt)
    {
        int ans=0;
        if(ll<=l && rr>=r)
            return tree[rt].len;
        int mid=(l+r)>>1;
        if(ll<=mid)
            ans=max(ans,query(ll,rr,lson));
        if(rr>mid)
            ans=max(ans,query(ll,rr,rson));
        if(a[mid]<a[mid+1])
        {
            if(ll<=mid && mid<rr)
                ans=max(ans,min(mid-ll+1,tree[rt<<1].rn)+min(rr-mid,tree[rt<<1|1].ln));
        }
        return ans;
    }
    int main()
    {
        int t,n,m;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            build(0,n-1,1);
            while(m--)
            {
                char ch[2];
                int x,y;
                scanf("%s%d%d",ch,&x,&y);
                if(ch[0]=='U')
                    updata(x,y,0,n-1,1);
                else
                {
                    int ans=query(x,y,0,n-1,1);
                    printf("%d\n",ans);
                }
            }
        }
        return 0;
    }
    

    展开全文
  • 所以用最长上升序列。找到最长的一个,其他的不往后放,就往前放。 n-len 就行,找最小的一个。 #include #include #include using namespace std; #define mem(v,x) memset(v,x,sizeof(v)) #define low(x) (x & ...

    You are given a sequence (P1,P2,…,PN) which is a permutation of the integers from 1 through N. You would like to sort this sequence in ascending order by repeating the following operation:

    • Choose an element in the sequence and move it to the beginning or the end of the sequence.

    Find the minimum number of operations required. It can be proved that it is actually possible to sort the sequence using this operation.

    Constraints

    • 1N2×105
    • (P1,P2,…,PN) is a permutation of (1,2,…,N).
    • All values in input are integers.
    Input

    Input is given from Standard Input in the following format:

    N
    P1
    :
    PN
    
    Output

    Print the minimum number of operations required.

    Sample Input 1

    4
    1
    3
    2
    4
    
    Sample Output 1

    2
    

    For example, the sequence can be sorted in ascending order as follows:

    • Move 2 to the beginning. The sequence is now (2,1,3,4).
    • Move 1 to the beginning. The sequence is now (1,2,3,4).
    Sample Input 2

    6
    3
    2
    5
    1
    4
    6
    
    Sample Output 2

    4
    
    Sample Input 3

    8
    6
    3
    1
    2
    7
    4
    8
    5
    
    Sample Output 3

    5

    这个题是可以 既往后放,又可以往前放。

    我一开始就想的是逆序对,结果逆序对只可以只往一个方向放,不能既往前放,又往后放。4 2 3  1,是个反例

    所以用最长上升序列。找到最长的一个,其他的不往后放,就往前放。  n-len 就行,找最小的一个。




    #include <cstdio>
    #include<cstring>
    #include <algorithm>
    using  namespace std;
    #define mem(v,x) memset(v,x,sizeof(v))
    #define low(x) (x & (-x))
    int pos[500010],n,m;
    
    int main() {
        scanf("%d",&n);
        for (int i = 1; i <= n; i++){
           scanf("%d",&m);
           pos[m] = i;
        }
        int len = 1,ans = 5000000;
        for (int i = 1; i < n; i++){
            if (pos[i+1] > pos[i]) len++; else{
                ans = min(ans,n-len);
                len = 1;
            }
        }
        ans = min(ans,n-len);
        printf("%d\n",ans);
    
        return 0;
    }

    展开全文
  • 题意:求区间连续递增的最大个数,Q是询问区间内最大的LCIS U是更新节点   #include #include #include using namespace std; const int maxn = 1e5 + 6 ; int llen[maxn 2 ], rlen...

    LCIS

    Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
    Total Submission(s): 9713    Accepted Submission(s): 4215


    Problem Description
    Given n integers.
    You have two operations:
    U A B: replace the Ath number by B. (index counting from 0)
    Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
     

     

    Input
    T in the first line, indicating the case number.
    Each case starts with two integers n , m(0<n,m<=105).
    The next line has n integers(0<=val<=105).
    The next m lines each has an operation:
    U A B(0<=A,n , 0<=B=105)
    OR
    Q A B(0<=A<=B< n).
     

     

    Output
    For each Q, output the answer.
     

     

    Sample Input
    1
    10 10
    7 7 3 3 5 9 9 8 1 8
    Q 6 6
    U 3 4
    Q 0 1
    Q 0 5
    Q 4 7
    Q 3 5
    Q 0 2
    Q 4 6
    U 6 10
    Q 0 9
     

     

    Sample Output
    1
    1
    4
    2
    3
    1
    2
    5
     
    题意:求区间连续递增的最大个数,Q是询问区间内最大的LCIS

    U是更新节点

     
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 1e5 + 6;
    int llen[maxn << 2], rlen[maxn << 2], len[maxn << 2], tree[maxn];
    void pushup(int l, int r, int id)
    {
        int m = (l + r) >> 1;
        llen[id] = llen[id << 1];
        rlen[id] = rlen[id << 1 | 1];
        if (tree[m + 1] > tree[m])
        {
            if (llen[id << 1] == m - l + 1)
                llen[id] += llen[id << 1 | 1];
            if (rlen[id << 1 | 1] == r - m)
                rlen[id] += rlen[id << 1];
            len[id] = max(max(len[id << 1], len[id << 1 | 1]), rlen[id << 1] + llen[id << 1 | 1]);
        }
        else
            len[id] = max(len[id << 1], len[id << 1 | 1]);
    }
    void build(int l, int r, int id)
    {
        if (l == r)
        {
            scanf("%d", &tree[l]);
            len[id] = llen[id] = rlen[id] = 1;
            return;
        }
        int m = (l + r) >> 1;
        build(l,m,id<<1);
        build(m+1,r,id<<1|1);
        pushup(l, r, id);
    }
    int query(int ll, int rr, int l, int r, int id)
    {
        if (ll <= l && r <= rr)
            return len[id];
        int m = (l + r) >> 1;
        if (ll <= m && m < rr)
        {
            int l1 = query(ll, rr, l,m,id<<1);
            int l2 = query(ll, rr, m+1,r,id<<1|1);
            if (tree[m] < tree[m + 1])
            {
                int le = max(ll, m - rlen[id << 1] + 1);
                int ri = min(rr, m + llen[id << 1 | 1]);
                return max(max(l1, l2), ri - le + 1);
            }
            return max(l1, l2);
        }
        else if (rr <= m)
            return query(ll, rr, l,m,id<<1);
        else
            return query(ll, rr, m+1,r,id<<1|1);
    }
    
    void update(int a, int b, int l, int r, int id)
    {
        if (a == l && a == r)//找到要更新的位置
        {
            tree[a] = b;
            return;
        }
        int m = (l + r) >> 1;
        if (m >= a)
            update(a, b, l,m,id<<1);
        else
            update(a, b, m+1,r,id<<1|1);
        pushup(l, r, id);
    }
    int main()
    {
        int t;
        scanf("%d\n", &t);
        while (t--)
        {
            int n, m;
            scanf("%d%d", &n, &m);
            build(0, n - 1, 1);
    
            while (m--)
            {
                char c[5];
                int a, b;
                scanf("%s %d %d", c, &a, &b);
                if (c[0] == 'Q')
                    printf("%d\n", query(a, b, 0, n - 1, 1));
                else
                    update(a, b, 0, n - 1, 1);
            }
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/-citywall123/p/11066942.html

    展开全文
  • 这是一个最长连续上升序列的一个翻版,二话不说先上题 输入数据 输入的第一行是序列的长度N (1 <= N <= 1000)。 第二行给出序列中的N 个整数,这些整数的取值范围都在0 到10000。 输出要求 最长上升子...
  • 题目:给定一个无序的整数数组,找到其中最长上升序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长上升序列是 [2,3,7,101],它的长度是 4。 理解:由于题目只要最长上升序列得长度,并不...
  • 最长上升连续序列 II  给定一个整数矩阵(其中,有 n 行, m 列),请找出矩阵中的最长上升连续序列。(最长上升连续序列可从任意行或任意列开始,向上/下/左/右任意方向移动)。 样例 ...
  • 动态规划——最长连续上升序列 问题内容 输入: 一组可比较元素组成的序列 输出: 元素连续上升的最长一段子序列的长度以及该子序列 问题分析 采用动态规划的思想,维护一个一维数组s[i] 该数组记录的是原数组...
  • //最大连续序列和  #include&lt;string.h&gt;//最大连续序列  #include&lt;string&gt;//杭电1003  #include&lt;iostream&gt; #include&lt;algorithm&gt; using namespace ...
  • 最长连续上升序列

    2016-07-30 12:41:31
    贴一个最长连续上升序列的模板:#include using namespace std; int main(){ int n,a[100005]; scanf("%d",&n); for(int i = 0 ;i ;i++) scanf("%d",&a[i]); int len = 1,maxn = 1; for(int i =
  • 文章目录最长上升( 递增 )子序列最长连续上升( 递增 )子序列( LIS )1. 最长上升子序列题目描述说明暴力 dp 解法转化为LCS求解二分查找+贪心2.最长连续上升序列题目描述dp 解法3. 最长递增子序列的个数...
  • 最长上升连续序列

    千次阅读 2016-06-14 16:53:39
    题目描述:给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续序列。(最长上升连续序列可以定义为从右到左或从左到右的序列。) 样例:给定 [5, 4, 2, 1, 3], 其最长...
  • 397. 最长上升连续序列 最长上升连续序列 给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续序列。(最长上升连续序列可以定义为从右到左或从左到右的序列。) ...
  • 最长连续上升序列 AC: #include #include #include using namespace std; int a[50005],b[50005]; int main() { int ans,n; while(~scanf("%d",&n)) { memset(b,0,sizeof(b)); ans=0; for(int i=1;i;++i) ...
  • 300. 最长上升序列 题目描述 给定一个无序的整数数组,找到其中最长上升序列的长度。 解题思路 1. 动态规划 状态:dp[i]dp[i]dp[i] 表示长度为iii的序列最长上升序列的长度 状态转移方程:递增序列,只需要...
  • 最大和最长也不一样,最大是求子序列加起来的数值最大,最长是这个子序列的长度最长。 最大连续序列和或者 最大连续序列 其实可以叫做最大子串和 求一个数列的最大的连续序列的和是多少,通常还要得到是...
  • 397. 最长上升连续序列 中文English 给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续序列。(最长上升连续序列可以定义为从右到左或从左到右的序列。) 样例 ...
  • 最长上升序列问题(中等) 题目描述 给定一个无序的整数数组,找到其中最长上升序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长上升序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有...
  • 给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续序列。(最长上升连续序列可以定义为从右到左或从左到右的序列。) 样例 给定[5, 4, 2, 1, 3], 其最长上升...

空空如也

空空如也

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

最长连续上升序列