数列(seq)

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/1157

Description

给出一个长度为n的数列A。现有如下两种操作：

修改操作：把数列中第i个数改为x

询问操作：给定一个位置i，问数列中有多少个位置j ( j>i )，满足位置i与位置j间所有的数都不超过Ai与Aj的较大值。

现共有m个操作，请对每个询问操作做出回答。

Input

第一行两个正整数n、m。

随后n行，每行一个正整数Ai。

随后m行，若是修改操作，则以一个大写C开头，随后两个正整数i和x；若是查询操作，则以一个大写Q开头，随后一个正整数i。

Output

每行一个整数，依次对每个询问操作给出回答。

Sample Input

5 3

Q 1

C 1 3

Q 1

Sample Output

HINT

对于40%的数据，n、m<=5000

对于100%的数据，n、m<=50000，|Ai|、x<=100000

题意

题解：

简单分析一下，就知道，他是让你求有多少个数在他右边比他小

然后再求一个不递减的序列长度

假设，ans[x]表示以a[x]开头的单调不减序列的长度的话

如果查询的位置是x的话，有y个数在他右边比他小，那么答案就是y+ans[y+1]

--------------------

具体做法的话：

如果不分块的话，根本不会……

右边有多少个比他小的，就用线段树来二分就好了

不递减的序列长度，就用分块来维护就好了

代码：

//qscqesze#pragma comment(linker, "/STACK:1024000000,1024000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 200006#define mod 1000000007#define eps 1e-9#define e exp(1.0)#define PI acos(-1)#define lowbit(x) (x)&(-x)const double EP = 1E-10 ;int Num;//const int inf=0x7fffffff;const ll inf=999999999;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//*************************************************************************************int n;int a[maxn];struct data{ int l,r,mn;}tr[maxn*4];void build(int k,int s,int t){ tr[k].l=s;tr[k].r=t; if(s==t){tr[k].mn=a[s];return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].mn=max(tr[k<<1].mn,tr[k<<1|1].mn);}int ask(int k,int s,int t){ int l=tr[k].l,r=tr[k].r; if(s==l&&t==r)return tr[k].mn; int mid=(l+r)>>1; if(t<=mid)return ask(k<<1,s,t); if(s>mid)return ask(k<<1|1,s,t); return max(ask(k<<1,s,mid),ask(k<<1|1,mid+1,t));}void update(int k,int x,int y){ int l=tr[k].l,r=tr[k].r; if(l==r){tr[k].mn=y;return;} int mid=(l+r)>>1; if(x<=mid)update(k<<1,x,y); if(x>mid)update(k<<1|1,x,y); tr[k].mn=max(tr[k<<1].mn,tr[k<<1|1].mn);}int l[300],r[300];int belong[50001];int block;vector
                    
                      Q[500];int ans[maxn];int num;int main(){ n = read(); int q=read(); for(int i=1;i<=n;i++) a[i]=read(); block = sqrt(n); int num = n/block; if(n%block)num++; for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block; r[num]=n; for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1; for(int i=1;i<=num;i++) { int tmp = 0; for(int j=l[i];j<=r[i];j++) { if(a[j]>=tmp) { Q[i].push_back(a[j]); tmp = a[j]; } } } build(1,1,n); char c[5]; while(q--) { scanf("%s",c); if(c[0]=='Q') { int x=read(); int L = x+1 , R = n; while(L<=R) { int mid = (L+R)>>1; if(ask(1,x+1,mid)<=a[x]) L = mid+1; else R = mid-1; } //cout<
                     
                      <
                      
                       =tmp) { Ans++; tmp = a[i]; } } for(int i=k+1;i<=num;i++) { if(!Q[i].empty()) { if(tmp>Q[i][Q[i].size()-1]) continue; Ans+=Q[i].end()-lower_bound(Q[i].begin(),Q[i].end(),tmp); tmp = Q[i][Q[i].size()-1]; } } } printf("%d\n",Ans + ans[x]); } else { int x=read(); int y=read(); a[x]=y; update(1,x,y); int k = belong[x]; Q[belong[x]].clear(); int tmp = 0; for(int i=l[k];i<=r[k];i++) { if(a[i]>=tmp) { Q[k].push_back(a[i]); tmp = a[i]; } } } }}

转载地址：http://buozl.baihongyu.com/

你可能感兴趣的文章

Spring Cloud Alibaba基础教程：Nacos配置的多环境管理