SumoandFibonacci

C++14(g++5.4) 解法, 执行用时: 745ms, 内存消耗: 6620K, 提交时间: 2020-07-06 22:48:17

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+100;
const int mod=1e9+7;
typedef long long ll;
int a[maxn],t[maxn];
int cnt[maxn];
int belong[maxn];
int n,m,size,bnum,tt;
ll now,ans[maxn],f[maxn];
struct node {
	int l,r;
	ll now;
	ll pre;
	ll size;//记录左子树节点数 
}segTree[maxn*4];
void pushup (int i) {
	int k=segTree[i<<1].size;
	segTree[i].size=segTree[i<<1].size+segTree[i<<1|1].size;
	segTree[i].pre=segTree[i<<1].pre+segTree[i<<1|1].pre*(k>0?f[k-1]:1)+segTree[i<<1|1].now*f[k];
	segTree[i].pre%=mod;
	segTree[i].now=segTree[i<<1].now+segTree[i<<1|1].pre*f[k]+segTree[i<<1|1].now*f[k+1];
	segTree[i].now%=mod;
}

void build (int i,int l,int r) {
	segTree[i].l=l;
	segTree[i].r=r;
	segTree[i].now=0;
	segTree[i].pre=0;
	segTree[i].size=0;
	if (l==r) {
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	//pushup(i);
}
void update (int i,int x,int b) {
	if (segTree[i].l==segTree[i].r) {
		segTree[i].now+=b*t[x];
		segTree[i].size+=b;
		return;
	}
	int mid=(segTree[i].l+segTree[i].r)>>1;
	if (x<=mid)
		update(i<<1,x,b);
	if (x>mid)
		update(i<<1|1,x,b);
	pushup(i);
}




struct query {
	int l,r,id;
}q[maxn];
int cmp (query a,query b) {
    return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
} 
void add(int pos) {
	if (!cnt[a[pos]]) {
		//说明插入新数
		update(1,a[pos],1);
	}
    ++cnt[a[pos]];
    
}
void del(int pos) {
    --cnt[a[pos]];
    if (!cnt[a[pos]]) {
    	update(1,a[pos],-1);
	}
}
map<pair<int,int>,ll> mp;
int main () { 
    scanf("%d",&n);
    f[1]=f[2]=1;
    for (int i=3;i<=maxn;i++) f[i]=f[i-1]+f[i-2],f[i]%=mod;    
    size=sqrt(n);
	bnum=n/size+(n%size>0);
    for (int i=1;i<=bnum;i++) 
        for (int j=(i-1)*size+1;j<=i*size;j++)
            belong[j]=i;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),t[i]=a[i];
    sort(t+1,t+n+1);
    tt=unique(t+1,t+n+1)-t-1;
    build(1,1,tt+2);
    //printf("%d\n",tt);
    for (int i=1;i<=n;i++) a[i]=upper_bound(t+1,t+tt+1,a[i])-t-1;
    //for (int i=1;i<=n;i++) printf("%d\n",a[i]);
    scanf("%d",&m);
    for (int i=1;i<=m;i++) {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for (int i=1;i<=m;i++) {
        int ql=q[i].l;
        int qr=q[i].r;
        if (mp[make_pair(ql,qr)]) {
        	ans[q[i].id]=mp[make_pair(ql,qr)];
        	continue;
		}
        while (l<ql) del(l++);
        while (l>ql) add(--l);
        while (r<qr) add(++r);
        while (r>qr) del(r--);
		
		ans[q[i].id]=segTree[1].now;
		mp[make_pair(ql,qr)]=segTree[1].now;
    }
    for (int i=1;i<=m;i++) cout<<ans[i]<<"\n"; 
}

C++11(clang++ 3.9) 解法, 执行用时: 1415ms, 内存消耗: 3556K, 提交时间: 2020-06-06 16:46:44

#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 3e4+7;
const int mod = 1e9+7;

int n, m, len;
int c[maxn], cnt[maxn], b[maxn];
int ans[maxn], fib[maxn];

struct Q{
    int l, r, id;
    friend bool operator < (const Q &a, const Q &b) {
        if((a.l-1)/len==(b.l-1)/len) {
            if((a.l-1)/len%2) return a.r>b.r;
            return a.r<b.r;
        }
        return a.l<b.l;
    }
}q[maxn];

map<pr,int> vis;

int main() {
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
    fib[1]=fib[2]=1;
    for(int i=3; i<maxn; ++i) fib[i]=(fib[i-1]+fib[i-2])%mod;
    n=read(); len=ceil(sqrt(n));
    for(int i=1; i<=n; ++i) b[i]=c[i]=read();
    sort(b+1,b+1+n); int nn=unique(b+1,b+1+n)-b-1;
    for(int i=1; i<=n; ++i) c[i]=lower_bound(b+1,b+1+nn,c[i])-b;
    //for(int i=1; i<=n; ++i) see(c[i]);
    m=read();
    for(int i=1; i<=m; ++i) {
        int l=read(), r=read();
        q[i]=(Q){l,r,i};
    }
    sort(q+1,q+1+m);
    int l=1, r=0;
    for(int i=1; i<=m; ++i) {
        if(vis.count(pr(q[i].l,q[i].r))) {
            ans[q[i].id]=vis[pr(q[i].l,q[i].r)];
            continue;
        }
        while(l>q[i].l) ++cnt[c[--l]];
      	while(r<q[i].r) ++cnt[c[++r]];
        while(l<q[i].l) --cnt[c[l++]];
        while(r>q[i].r) --cnt[c[r--]];
        ll tmp=0;
        for(int j=1, t=0; j<=nn; ++j) if(cnt[j]) {
            tmp+=ll(b[j])*fib[++t]%mod;
            //if(q[i].id==1) see(q[i].l), see(q[i].r), see(b[j]), see(t);
            //if(tmp>=mod) tmp-=mod;
        }
        ans[q[i].id]=tmp%mod;
        vis[pr(l,r)]=tmp%mod;
    }
    for(int i=1; i<=m; ++i) printf("%d\n", ans[i]);
}

详情