锐客网

  1. 首页 > 睿知 > it技术 > >

HDU暑假多校第八场J-Taotao Picks Apples

IT知识暑假多校taotao

历览千载书，时时见遗烈。这篇文章主要讲述HDU暑假多校第八场J-Taotao Picks Apples相关的知识，希望能为你提供帮助。
一、题意给定一个序列，之后给出若干个修改，修改的内容为在原序列的基础上，将某一位元素的值改成给定的值< 每次修改相互独立，不保存修改后的结果> 。之后询问，在选择第一位元素的情况下，最长递增子序列的长度是多少。
二、题解考虑不经修改的情况，应当设dp[i]为选取当前位情况下的最长递增子串的长度。则对于这道题，应当认为对于修改a为b，设l_pos为a左边最大的元素的位置，r_pos为a右边大于max(b,r_pos)的元素的位置。则有ans = dp[1] - dp[l_pos] + 1 + dp[r_pos]; 对于b本身大于位于l_pos的元素，应当给结果+1。
【HDU暑假多校第八场J-Taotao Picks Apples】 

#include< bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 1000233; class Node{ public: int l,r,lc,rc,maxx; }; Node nodes[MAXN]; int nodes_num; int t,n,m; int arr[MAXN]; int dp[MAXN]; void tree_init(int a,int b){ int now = nodes_num++; nodes[now].l = a; nodes[now].r = b; if(a == b-1){ nodes[now].maxx = arr[a]; return ; } int mid = (a+b)/2; nodes[now].lc = nodes_num; tree_init(a,mid); nodes[now].rc = nodes_num; tree_init(mid,b); nodes[now].maxx = max(nodes[nodes[now].lc].maxx,nodes[nodes[now].rc].maxx); }int find_max(int now){ int l = nodes[now].l; int r = nodes[now].r; if(l == r-1)return l; int maxx = nodes[now].maxx; int lc = nodes[now].lc; int rc = nodes[now].rc; if(maxx == nodes[lc].maxx)return find_max(lc); else return find_max(rc); }int find_biggest(int now,int a,int b){ int l = nodes[now].l; int r=nodes[now].r; if(l == a& & r == b){ return find_max(now); } int mid = (l+r)/2; int ret ; int lc = nodes[now].lc; int rc = nodes[now].rc; if(a< mid){ ret = find_biggest(lc,a,min(b,mid)); if(b> mid){ int tmp = find_biggest(rc,mid,b); ret = arr[ret] > = arr[tmp] ? ret:tmp; } }else ret = find_biggest(rc,a,b); return ret; }int find_left(int now,int key){ int l = nodes[now].l; int r = nodes[now].r; if(l == r-1)return l; int lc = nodes[now].lc; int rc = nodes[now].rc; if(nodes[lc].maxx > key)return find_left(lc,key); else return find_left(rc,key); }int find_first(int now,int pos, int key){ int l = nodes[now].l; int r = nodes[now].r; if(l > = pos){ return find_left(now,key); } int mid = (l+r)/2; int lc = nodes[now].lc; int rc = nodes[now].rc; int ret ; if(pos < mid & & nodes[lc].maxx > key){ ret = find_first(lc,pos,key); if(ret > = pos & & arr[ret] > key)return ret; } if(nodes[rc].maxx < = key)return r-1; return find_first(rc,pos,key); }void init(){ scanf("%d %d",& n,& m); nodes_num = 0; arr[0] = -100233; arr[n+1] = INT_MAX; for(int i=1; i< =n; ++i)scanf("%d",& arr[i]); tree_init(0,n+2); memset(dp,0,sizeof(dp)); for(int i=n; i> =1; --i){ dp[i] = dp[find_first(0,i+1,arr[i])]+1; } dp[0] = dp[1]+1; for(int i=0; i< m; ++i){ int a,b; scanf("%d %d",& a,& b); int l_pos = find_biggest(0,0,a); int key = max(b,arr[l_pos]); int r_pos = find_first(0,a+1,max(b,arr[l_pos])); int ans = dp[1] - dp[l_pos] + 1 + dp[r_pos]; if(b > arr[l_pos] )ans++; cout< < ans< < ‘ ‘; }}int main(){cin> > t; while(t--)init(); return 0; }

 

    推荐阅读


    上一篇：hdu 6406Taotao Picks Apples

    下一篇：appium 环境准备