Hướng dẫn giải của Dãy số


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int n,f[100100];
long long re,L,R,a[100100];
vector <long long> X;

void add(int x)
{
    x++;
    while (x<=int(X.size())) f[x]++, x+=x&-x;
}

int get(int x)
{
    int r=0;
    x++;
    while (x) r+=f[x],x-=x&-x;
    return r;
}

int main()
{
    int x;
    cin >> n >> L >> R;
    X.push_back(0);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        a[i]=a[i-1]+x;
        X.push_back(a[i]);
    }
    sort(X.begin(),X.end());
    X.resize(unique(X.begin(),X.end())-X.begin());
    for (int i=0;i<=n;i++)
    {
        if (i)
        {
            int low=lower_bound(X.begin(),X.end(),a[i]-R)-X.begin();
            int high=upper_bound(X.begin(),X.end(),a[i]-L)-X.begin();
            if (low<high)   re+=get(high-1)-get(low-1);
        }
        x=lower_bound(X.begin(),X.end(),a[i])-X.begin();
        add(x);
    }   
    cout << re << endl;
    return 0;
}

Code mẫu của happyboy99x

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int a[N], bit[3*N], n, l, r, maxID;
long long t[3*N], s[N];
map<long long, int> cmprs; //compress

void enter() {
    scanf("%d%d%d", &n, &l, &r);
    for(int i = 1; i <= n; ++i) scanf("%d", a+i);
}

void compress() {
    for(int i = 0; i <= n; ++i) {
        if(i) s[i] = s[i-1] + a[i];
        t[3*i] = s[i]; t[3*i+1] = s[i]-l+1, t[3*i+2] = s[i]-r;
    }
    sort(t, t+3*(n+1));
    const int &x = maxID = unique(t, t+3*(n+1)) - t;
    for(int i = 0; i <= n; ++i) {
        cmprs[s[i]] = x - (lower_bound(t, t+x, s[i]) - t);
        cmprs[s[i]-l+1] = x - (lower_bound(t, t+x, s[i]-l+1) - t);
        cmprs[s[i]-r] = x - (lower_bound(t, t+x, s[i]-r) - t);
    }
}

void Inc(int v) {
    for(; v <= maxID; v += v & -v) ++bit[v];
}

int sumTo(int v) {
    int res = 0;
    for(; v > 0; v -= v & -v) res += bit[v];
    return res;
}

void solve() {
    long long res = 0;
    for(int i = 0; i <= n; ++i) {
        res += sumTo(cmprs[s[i]-r]) - sumTo(cmprs[s[i]-l+1]);
        Inc(cmprs[s[i]]);
    }
    printf("%lld\n", res);
}

int main() {
    enter();
    compress();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

long long a[N];
long long t[N];
long long L, R;
int n;

long long solve(int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    long long ans = solve(l, mid) + solve(mid + 1, r);
    int pl = mid + 1, pr = mid + 1;
    for (int i = r; i > mid; --i) {
        while (pl > l && a[i] - a[pl - 1] < L) --pl;
        while (pr > l && a[i] - a[pr - 1] <= R) --pr;
        if (pl > pr) ans += pl - pr;
    }
    merge(a + l, a + mid + 1, a + mid + 1, a + r + 1, t);
    for (int i = l, j = 0; i <= r; ++i, ++j) a[i] = t[j];
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("C11SEQ.txt", "r", stdin);
#endif // ONLINE_JUDGE
    cin >> n >> L >> R;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    cout << solve(0, n) << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (feof(stdin)) memset(BUF, 0, sizeof BUF); else fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const int MN = 100111;

int n, s;
long long a[MN], c[MN], l, r;
long long bit[MN];

#define _(x) ((x) & (-(x)))

void update(int x) {
    while (x <= 100000) {
        bit[x] ++;
        x += _(x);
    }
}

long long get(int x) {
    if (x < 0) return 0;
    long long res = 0;
    while (x) {
        res += bit[x];
        x -= _(x);
    }
    return res;
}

void RR() {
    FOR(i,1,n) c[i] = a[i];
    sort(c+1, c+n+1);
    s = unique(c+1, c+n+1) - c - 1;
    FOR(i,1,n) a[i] = lower_bound(c+1, c+s+1, a[i]) - c;
    ++s; c[s] = 1000111000111000111LL;
}

long long cal(long long x) {
    memset(bit, 0, sizeof bit);
    long long res = 0;
    FORD(i,n,0) {
        int u = upper_bound(c+1, c+s+1, c[a[i]] + x) - c - 1;
        res += get(u);
        if (i) update(a[i]);
    }
    return res;
}

int main() {
    GN(n); GN(l); GN(r); FOR(i,1,n) GN(a[i]);
    FOR(i,1,n) a[i] += a[i-1];
    RR();
    cout << cal(r) - cal(l-1) << endl;
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 100111
#define oo 1111111111
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,l,r;
long long a[maxn],b[maxn];

long long Search(long long x,int first,int last){
      int mid;
      first--;
      last++;
      while(first+1!=last){

            mid = (last+first)/2;
            if(x>a[mid])
                   first = mid;
            else last = mid;
            //if(x==5) printf("555 %d %lld %lld\n",mid,x,a[mid]);
      }
      return first;
}

long long mergesort(int dau,int cuoi){
      int mid;
      int i,j;
      long long KQ = 0;
      if(dau == cuoi){
           if(a[dau]-a[dau-1]>=l && a[dau]-a[dau-1]<=r)
                return 1;
           else return 0;
      }
      mid = (dau+cuoi)/2;
      KQ = mergesort(dau,mid)+mergesort(mid+1,cuoi);
      for(i = dau;i<=mid;i++){
            //if(dau==1 && mid ==2) printf("llllll %d  %lld %lld %lld\n",i,a[i-1],Search(a[i-1]+r+1,mid+1,cuoi),Search(a[i-1]+l,mid+1,cuoi));
           KQ += Search(a[i-1]+r+1,mid+1,cuoi)-Search(a[i-1]+l,mid+1,cuoi);
      }
      for(i = mid;i>=dau;i--) b[i] = a[i]; i++;
      for(j =mid+1;j<=cuoi;j++)  b[cuoi+mid+1-j] = a[j]; j--;
      for(mid = dau; mid <= cuoi; mid++){
            if (b[i]<b[j]){
                a[mid]=b[i]; i++;
            }
            else {
                a[mid]=b[j]; j--;
            }
      } 
      //printf("%d %d %d\n",dau,cuoi,KQ);
      return KQ;          
}

int main(){
    //freopen("C11SEQ.in","r",stdin);
    scanf("%d %d %d",&n,&l,&r);
    //printf("%d %d %d\n",n,l,r);
    a[0] = 0;
    for(int i = 1;i<=n;i++)
    {
          scanf("%lld",&a[i]);
          a[i] += a[i-1];
        //  printf("%d %lld\n",i,a[i]);
    }
    printf("%lld",mergesort(1,n));
    //getch();
}

Code mẫu của skyvn97

#include<cstdio>
#include<algorithm>
#define MAX   100100
using namespace std;
typedef long long ll;
ll a[MAX];
ll s[MAX];
ll v[3*MAX];
ll l,r;
ll t[3*MAX];
int n;
int cs[MAX];
int cl[MAX];
int cr[MAX];
void init(void) {
    scanf("%d",&n);
    scanf("%lld",&l);
    scanf("%lld",&r);
    int i;
    s[0]=0;
    for (i=1;i<=n;i=i+1) {
        scanf("%lld",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    for (i=0;i<=3*n+10;i=i+1) t[i]=0;
}
void compress(void) {
    int i;
    for (i=0;i<=n;i=i+1) {
        v[3*i+1]=s[i];
        v[3*i+2]=s[i]+l;
        v[3*i+3]=s[i]+r;
    }
    sort(&v[1],&v[3*n+4]);
    for (i=0;i<=n;i=i+1) {
        cs[i]=lower_bound(&v[1],&v[3*n+4],s[i])-&v[0]+1;
        cl[i]=lower_bound(&v[1],&v[3*n+4],s[i]+l)-&v[0]+1;
        cr[i]=lower_bound(&v[1],&v[3*n+4],s[i]+r)-&v[0]+1;
    }
}
void update(int x) {
    while (1<=x && x<=3*n+10) {
        t[x]++;
        x=x+(x&(-x));
    }
}
ll get(int x) {
    ll res=0;
    while (1<=x && x<=3*n+10) {
        res=res+t[x];
        x=x&(x-1);
    }
    return (res);
}
ll sum(int a,int b) {
    return (get(b)-get(a-1));
}
void process(void) {
    int i;
    ll res=0;
    for (i=n;i>=0;i=i-1) {
        res=res+sum(cl[i],cr[i]);
        update(cs[i]);
    }
    printf("%lld\n",res);
}
int main(void) {
    init();
    compress();
    process();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.