Educational codes round 65

I haven't been blogging for a long time

E. Range Deleting

meaning of the title

Give you a sequence \ (a_1, a_2, dots a_n \) with the length of \ (n \), and define \ (f(l,r) \) as the sequence after deleting the \ (l\le a_i\le r \) element. Find the number of all (f(l,r) \) monotone sequences.

\(n,a_i\le 10^6\)

Title Solution

Simple questions, but still adjusted for a year (see code Notes).

Consider that the deleted interval must be a prefix and a suffix. First, find a legal extremely long suffix, and then enumerate the prefixes. Under the condition of ensuring the prefix is legal, count the number of legal suffixes with two pointers. Complexity \ (O(n) \).

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gi()
{
    char c=getchar(); int x=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
    return x;
}
const int N=1e6+5;
int a[N],n,x,ans,fst[N],lst[N],gst[N];
int main()
{
    #ifdef lc
        freopen("in.txt","r",stdin);
    #endif
    n=gi(),x=gi();
    memset(fst,0x3f,sizeof(fst));
    for(int i=1;i<=n;++i)
    {
        a[i]=gi();
        if(fst[a[i]]==fst[0]) fst[a[i]]=i;
        lst[a[i]]=i;
    }
    int r=x,f=fst[x]; gst[x]=fst[x];
    for(;r>=1;--r)
    {
        if(gst[r]<lst[r-1]) break;
        gst[r-1]=min(gst[r],fst[r-1]);
    }
    if(!r)
    {
        printf("%I64d",1ll*x*(x+1)/2);
        return 0;
    }
    int l=0;
    long long ans=0;
    for(int i=1;i<=x;++i)
    {
        for(r=max(r,i);r<=x&&gst[r]<l;++r);
        ans+=x-r+2; //Note that you can't -- r, ans+=x-r+1
        if(fst[i]<l) break;
        l=max(l,lst[i]);
    }
    printf("%I64d",ans);
}

F. Scalar Queries

meaning of the title

Give you a sequence of \ (n \) in length (a_1, a_2, dots a_n \), set \ (f(l,r) \) equal to the sum of each number in the sequence \ ([l,r] \) multiplied by the rank in the current interval. Find \ (\ sum {1 \ Le L \ Le R \ Le n} f(l,r) \)

\(n\le 5\cdot 10^5, a_i\le 10^9\) .

Title Solution

It is simpler than the previous one, considering the contribution of the current number directly. After discretization, the two tree arrays directly maintain the number and subscript sum of the number smaller than the current number on the left and right. It's good to count them casually. \(O(n\log n)\) .

The code is a little ugly.

code

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e5+5,Mod=1e9+7;
int a[N],b[N],n,t1[N],t2[N],s1[N],s2[N],c[N],m,ans;
#define lowbit(x) (x&-x)
void upd(int* t, int i, int w) {
    for(;i<=m;i+=lowbit(i)) t[i]=((t[i]+w)%Mod+Mod)%Mod;
}
int qry(int* t, int i)
{
    int r=0;
    for(;i;i-=lowbit(i)) r=(r+t[i])%Mod;
    return r;
}
void add(int x) { ans=(ans+x)%Mod; }
int mul(int x, int y) {
    x=1ll*(x+Mod)%Mod, y=1ll*(y+Mod)%Mod;
    return 1ll*x*y%Mod;
}
int main()
{
    #ifdef lc
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]), c[i]=a[i];
    sort(c+1,c+1+n),m=unique(c+1,c+1+n)-c-1;
    for(int i=1;i<=n;++i)
    {
        b[i]=lower_bound(c+1,c+1+m,a[i])-c;
        upd(t2,b[i],1);
        upd(s2,b[i],i);
    }
    for(int i=1;i<=n;++i)
    {
        int x1=qry(t1,b[i]),y1=qry(s1,b[i]),x2=qry(t2,b[i]),y2=qry(s2,b[i]);
        add(mul(a[i],mul(i,((mul(n+1,x2)-y2)%Mod+Mod)%Mod)));
        add(mul(a[i],mul(n-i+1,y1)));
        upd(t2,b[i],-1),upd(s2,b[i],-i);
        upd(t1,b[i],1),upd(s1,b[i],i);
    }
    printf("%d",ans);
}

Tags: PHP

Posted on Sat, 02 Nov 2019 12:47:45 -0700 by johnoc