0

给定一个包含N个元素的数组，我需要找到L和R的T个不同值的最长递增子序列的长度。我尝试了分段树，但超出了时间限制。

using namespace std;


  int a[1000001],ans[1000001],out;
  int T[1000001];
  int query(int v,int tl,int tr,int l,int r){
      if (l>r) return 0;
      if (tl==l && tr==r){
          return T[v];
      };
      int tm=(tl+tr)/2;
      return max(query(2*v,tl,tm,l,min(tm,r)),query(2*v+1,tm+1,tr,max(tm+1,l),r));
  };
  void update(int v,int tl,int tr,int pos,int val)
  {
       if (tl==tr){
          T[v]=val;
          return;
       };
       ll tm=(tl+tr)/2;
       if (tm>=pos) update(2*v,tl,tm,pos,val); else update(2*v+1,tm+1,tr,pos,val);
       T[v]=max(T[2*v],T[2*v+1]);
  };
int main()
{

        int n,i,t;
        cin>>n>>t;
       for (i=1;i<=n;i++)
          cin>>a[i];

        for(int j=0;j<t;j++)
        {
            int l,r;
           cin>>l>>r;
            for (i=l;i<=r;i++)
           { 
               ans[a[i]]=query(1,1,n,1,a[i]-1)+1;
               update(1,1,n,a[i],ans[a[i]]);
               out=max(out,ans[a[i]]);
           }

           cout<<out;
           out=0;

        }

    }


 return 0;
}

现在我需要找出每对L, R的 LIS 。有人可以帮助提高T查询的时间复杂度吗？

有没有办法使用单独的 for 循环计算每个查询的答案并删除嵌套的 for 循环并使用内部 for 循环一次计算整个数组的 LIS？

更新：之前的错误已解决，所以我更新了问题。

4

0 回答 0