In this HackerEarth Shil and Wave sequence problem solution we have given a sequence A1 , A2 , A3 .. AN of length N . Find total number of wave subsequences having length greater than 1.
Wave subsequence of sequence A1 , A2 , A3 .. AN is defined as a set of integers i1 , i2 .. ik such that Ai1 < Ai2 > Ai3 < Ai4 …. or Ai1 > Ai2 < Ai3 > Ai4 …. and i1 < i2 < …< ik.Two subsequences i1 , i2 .. ik and j1 , j2 .. jm are considered different if k != m or there exists some index l such that il ! = jl.
HackerEarth Shil and Wave sequence problem solution.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define inf 1e8
#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
#define mp make_pair
#define pb push_back
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)
ll bt[100011][2]={0};
ll a[100011];
ll bt1[100011]={0};
void update(int ind ,ll val,int pos){
while(ind<=100000){
bt[ind][pos]+=val;
bt[ind][pos]%=mod;
ind+=(ind&-ind);
}
}
ll query(int ind,int pos){
ll ans=0;
while(ind>0){
ans+=bt[ind][pos];
ans%=mod;
ind-=(ind&-ind);
}
return ans;
}
void update1(int ind ,ll val){
while(ind<=100000){
bt1[ind]+=val;
ind+=(ind&-ind);
}
}
ll query1(int ind){
ll ans=0;
while(ind>0){
ans+=bt1[ind];
ind-=(ind&-ind);
}
return ans;
}
int main(){
freopen("input-15.txt","r",stdin);
freopen("output-15.txt","w",stdout);
int N;
cin >> N;
rep(i,N){
cin >> a[i+1];
}
ll ans=0;
ll f,s;
for(int i=1;i<=N;i++){
f=query(a[i]-1,1);
s=query(100000,0)-query(a[i],0);
s+=mod;
s%=mod;
f+=query1(a[i]-1);
s=s+query1(100000)-query1(a[i]);
f%=mod;
s%=mod;
update1(a[i],1);
update(a[i],f,0);
update(a[i],s,1);
ans=ans+f+s;
ans%=mod;
}
cout<<ans;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define max 100002
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
ll tree[max][3];
ll read(ll idx, ll i) {
ll sum = 0;
while (idx > 0) {
sum += tree[idx][i];
if(sum > mod) sum %= mod;
idx -= (idx & -idx);
}
return sum;
}
void update(ll idx ,ll val, ll i) {
while (idx <= max) {
tree[idx][i] += val;
if(tree[idx][i] > mod) tree[idx][i] %= mod;
idx += (idx & -idx);
}
}
int main()
{
ll n,i,j;
cin>>n;
ll a[n];
for(i = 0; i < n; i++) {
cin>>a[i];
}
if(n == 1) {
puts("0");
return 0;
}
memset(tree,0,sizeof(tree));
ll ans = 0;
update(a[0],1,0);
update(a[0],0,1);
update(a[0],0,2);
for(i = 1; i < n; i++) {
ll x,y;
x = (read(a[i]-1,1) + read(a[i]-1,0))%mod;
y = (read(max-1,2) - read(a[i],2) + read(max-1,0) - read(a[i],0) + mod)%mod;
ans = (ans + x + y)%mod;
update(a[i],y,1);
update(a[i],x,2);
update(a[i],1,0);
}
cout<<ans<<endl;
return 0;
}