最长递增子序列的数量

 

dp...用树状数组维护一下len和cnt

 

1 //树状数组 dp 2 //求LIS的数量 3 #include 
        
          4 using namespace std; 5  6 const int mod = 1e9 + 7; 7 const int maxn = 50010; 8 struct Node{ 9     int len, cnt;10     Node(int len = 0, int cnt = 0) : len(len), cnt(cnt){}11     Node operator + (const Node &t) const{12         if(len < t.len) return t;13         if(len > t.len) return (*this);14         return Node(len, (cnt + t.cnt) % mod);15     }16 };17 struct Info{18     int x, pos;19     bool operator < (const Info &temp) const{20         if(x == temp.x) return pos > temp.pos;21         return x < temp.x;22     }23 };24 25 bool cmp(Info &a, Info &b){26     if(a.x == b.x) return a.pos > b.pos;27     return a.x < b.x;28 }29 Node c[maxn];30 Info a[maxn];31 32 int n;33 void add(int i, Node v){34     for(; i <= n; i += i & -i) c[i] = c[i] + v;35 }36 37 Node sum(int i){38     Node res;39     for(; i; i -= i & -i) res = res + c[i];40     return res;41 }42 43 int main(){44     while(scanf("%d", &n) != EOF){45         for(int i = 0; i < n; i++){46             scanf("%d", &a[i].x);47             a[i].pos = i + 1;48         }49         sort(a, a + n);50         Node ans;51         for(int i = 0; i < n; i++){52             Node temp = sum(a[i].pos);53             if(++temp.len == 1) temp.cnt = 1;54             ans = ans + temp;55             add(a[i].pos, temp);56         }57         cout<
         
          <
         
        

 

CDQ写法没看懂=_=

学会了再回来补上。。。