FZU2236 第十四个目标 dp+树状数组优化

时间：2021-08-31 07:32:17

分析：这种题烂大街，n^2，然后数据结构优化下到nlogn，离散化

#include <cstdio>

#include <cstring>

#include <queue>

#include <set>

#include <map>

#include <stack>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <cmath>

using namespace std;

typedef long long LL;

typedef pair<int,int>pii;

const int N=1e5+;

const int INF=0x3f3f3f3f;

const int mod=;

int p[N],n,a[N],c[N];

int cnt;

void add(int x,int t){

   for(int i=x;i<=cnt;i+=i&(-i))

     c[i]=(c[i]+t)%mod;

}

int ask(int x){

    if(x==)return ;

    int ans=;

    for(int i=x;i>;i-=i&(-i))

      ans=(ans+c[i])%mod;

    return ans;

}

int main(){

    while(~scanf("%d",&n)){

      for(int i=;i<=n;++i)

        scanf("%d",&a[i]),p[i]=a[i];

      sort(p+,p++n);

      cnt=unique(p+,p++n)-p-;

      memset(c,,sizeof(c));

      int ans=;

      for(int i=;i<=n;++i){

         int pos=lower_bound(p+,p++cnt,a[i])-p;

         int tmp=(ask(pos-)+)%mod;

         add(pos,tmp);

         ans=(ans+tmp)%mod;

      }

      printf("%d\n",ans);

    }

    return ;

}

相关文章