好 蠢 啊
A.
标准分治。每次从分治区间中找到最大值的位置m,设f[l,r]为[l,r]的答案，那么f[l,r]=f[l,m-1]+f[m+1,r]+跨过m点的贡献。
然后枚举小的区间放到大的区间中查就行了。复杂度nlog^2n。
TM的这5e5你给128M怎么回事。。。开6s又怎么回事。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 500050 #define maxq 10000050 using namespace std; int n,a[maxn],b[maxn],hash[maxn],tot=0,ls[maxq/10+1],rs[maxq/10+1],root,tot_pnt=0,cnt=0,kr=0; int p; struct seg_tr { int mx,pos; seg_tr (int mx,int pos):mx(mx),pos(pos) {} seg_tr () {} }s[maxq/10+1]; struct query { int pos,lim; }q1[maxq>>1],q2[maxq>>1]; int numq1=0,numq2=0,t[maxn]; long long ans=0; bool cmp(query x,query y) { return x.pos<y.pos; } int lowbit(int x) {return (x&(-x));} int read() { char ch;int data=0; while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') { data=data*10+ch-'0'; ch=getchar(); } return data; } void addq(int nows,int l,int r,int val) { if (l-1) { ++numq1; q1[numq1].pos=l-1; q1[numq1].lim=lower_bound(hash+1,hash+tot+1,val/a[nows])-hash; if (hash[q1[numq1].lim]!=(val/a[nows])) q1[numq1].lim--; } if (r) { ++numq2; q2[numq2].pos=r; q2[numq2].lim=lower_bound(hash+1,hash+tot+1,val/a[nows])-hash; if (hash[q2[numq2].lim]!=(val/a[nows])) q2[numq2].lim--; } } seg_tr combine(seg_tr x,seg_tr y) { if (x.mx>y.mx) return x; else return y; } void build(int &now,int left,int right) { now=++tot_pnt; if (left==right) {s[now]=seg_tr(a[left],left);return;} int mid=(left+right)>>1; build(ls[now],left,mid);build(rs[now],mid+1,right); s[now]=combine(s[ls[now]],s[rs[now]]); } seg_tr ask(int now,int left,int right,int l,int r) { if ((left==l) && (right==r)) return s[now]; int mid=(left+right)>>1; if (r<=mid) return ask(ls[now],left,mid,l,r); else if (l>=mid+1) return ask(rs[now],mid+1,right,l,r); else return combine(ask(ls[now],left,mid,l,mid),ask(rs[now],mid+1,right,mid+1,r)); } void conc1(int left,int right) { if (left>right) return; int pos=ask(root,1,n,left,right).pos; if (pos-left+1<=right-pos+1) for (int i=left;i<=pos;i++) addq(i,pos,right,a[pos]); else for (int i=pos;i<=right;i++) addq(i,left,pos,a[pos]); conc1(left,pos-1);conc1(pos+1,right); } void add(int pos,int val) { for (int i=pos;i<=tot;i+=lowbit(i)) t[i]+=val; } int ask(int pos) { int ret=0; for (int i=pos;i>=1;i-=lowbit(i)) ret+=t[i]; return ret; } int main() { n=read(); for (int i=1;i<=n;i++) { a[i]=read();b[i]=a[i];if (a[i]==1) cnt++; hash[++tot]=a[i]; } sort(hash+1,hash+tot+1);tot=unique(hash+1,hash+tot+1)-hash-1; for (int i=1;i<=n;i++) b[i]=lower_bound(hash+1,hash+tot+1,a[i])-hash; build(root,1,n); conc1(1,n); sort(q1+1,q1+numq1+1,cmp);sort(q2+1,q2+numq2+1,cmp); p=1; for (int i=1;i<=n;i++) { add(b[i],1); while (q1[p].pos==i) { ans-=ask(q1[p].lim); p++; } } p=1;memset(t,0,sizeof(t)); for (int i=1;i<=n;i++) { add(b[i],1); while (q2[p].pos==i) { ans+=ask(q2[p].lim); p++; } } printf("%lld ",ans-cnt); return 0; }
B.
打表发现，变换2^k次之后数组为b，那么b[i]=a[i]^a[i+2^k（从1..n旋转的意义下）]。
然后按照二进制按位算就行了。
考试的时候手推到第四次变换觉得一点规律没有。。然后瞬间觉得这是一个组合问题。。。然后又想到lucas。。。越来越远了。。。
二进制分组是个很重要的想法。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; long long n,m,a[maxn],b[maxn],tab[70]; long long read() { char ch;long long data=0; while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') { data=data*10+ch-'0'; ch=getchar(); } return data; } long long trans(long long x) { if (x<=n) return x; return (x-1)%n+1; } int main() { n=read();m=read();m--; for (long long i=1;i<=n;i++) a[i]=read(); tab[0]=1;for (long long i=1;i<=63;i++) tab[i]=tab[i-1]<<1; long long ret=0; while (m) { if (m&1) { for (long long i=1;i<=n;i++) b[i]=a[i]^a[trans(i+tab[ret])]; for (long long i=1;i<=n;i++) a[i]=b[i]; } m>>=1;ret++; } for (long long i=1;i<=n;i++) printf("%lld ",a[i]); printf(" "); return 0; }
C.
首先得到原式=Σ(i=1..√n)Σ(j=i+1..n/i) [gcd(i,j)=1]。
然后变成两段区间，直接2^质因子个数 容斥。
就完了
就完了
复杂度√nlogn。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 100500 using namespace std; long long n,prime[maxn],tot=0,w[maxn][60],ans=0,mn[maxn],f,kr=0; bool vis[maxn]; void get_table() { for (long long i=2;i<=maxn-500;i++) { if (!vis[i]) prime[++tot]=mn[i]=i; for (long long j=1;i*prime[j]<=maxn-500;j++) { vis[i*prime[j]]=true;mn[i*prime[j]]=prime[j]; if (i%prime[j]) continue;break; } } for (long long i=2;i<=maxn-500;i++) { long long ret=-1,x=i; while (x!=1) { if (mn[x]!=ret) {ret=mn[x];w[i][0]++;w[i][w[i][0]]=mn[x];} x/=mn[x]; } } } void dfs(long long now,long long top,long long ret,long long val,long long n) { if (now==w[top][0]+1) { if (!ret) return; if (ret&1) kr+=n/val;else kr-=n/val; return; } dfs(now+1,top,ret,val,n); dfs(now+1,top,ret+1,val*w[top][now],n); } void ask(long long n,long long val) {kr=0;dfs(1,val,0,1,n);} int main() { scanf("%lld",&n); get_table(); long long top=sqrt(n); for (long long i=2;i<=top;i++) { ask(n/i,i);ans+=(n/i)-kr; ask(i,i);ans-=i-kr; } printf("%lld ",ans); return 0; }