首页 > 代码库 > BZOJ3509: [CodeChef] COUNTARI

BZOJ3509: [CodeChef] COUNTARI

2024-08-08 12:56:26   216人阅读

3509: [CodeChef] COUNTARI

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 339  Solved: 85
[Submit][Status]

Description

给定一个长度为N的数组A[]，求有多少对i, j, k（1<=i<j<k<=N）满足A[k]-A[j]=A[j]-A[i]。

Input

第一行一个整数N（N<=10^5）。
接下来一行N个数A[i]（A[i]<=30000）。

Output

一行一个整数。

Sample Input

10
3 5 3 6 3 4 10 4 5 2

Sample Output

9

题解：

Mektpoy：

分成N/size块
对于三个数在同一块内
可以暴力size^2
对于两个数在同一块内
可以和上面一起暴力size^2
对于中间的数在当前块内 别的两个数不在当前块内
将两边卷积value*log(value)
 
时间复杂度 O(N*size+N/size*value*log(value))
size取2600左右可以达到比较满意的时间

感觉n*size已经超了。。。居然可过。。。orz
代码参考了云神的，感觉自己又没代码能力，思路又捉鸡，还怎么混啊。。。
代码：
  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 500000+5 26  27 #define maxm 20000000+5 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 1000000007 44  45 using namespace std; 46  47 inline int read() 48  49 { 50  51     int x=0,f=1;char ch=getchar(); 52  53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54  55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56  57     return x*f; 58  59 } 60 struct cp 61 { 62     double x,y; 63     cp operator +(cp b){return (cp){x+b.x,y+b.y};} 64     cp operator -(cp b){return (cp){x-b.x,y-b.y};} 65     cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};} 66 }; 67 int n,m,len,mx,num[maxn],l[maxn],r[maxn],st[maxn],ed[maxn],size,rev[maxn]; 68 cp a[maxn],b[maxn],c[maxn],y[maxn]; 69 const double PI=acos(-1.0); 70 void fft(cp *x,int n,int flag) 71 { 72     for0(i,n-1)y[rev[i]]=x[i]; 73     for0(i,n-1)x[i]=y[i]; 74     for(int m=2;m<=n;m<<=1) 75     { 76         cp wn=(cp){cos(2.0*PI/m*flag),sin(2.0*PI/m*flag)}; 77         for(int i=0;i<n;i+=m) 78         { 79             cp w=(cp){1,0};int mid=m>>1; 80             for0(j,mid-1) 81             { 82                 cp u=x[i+j],v=x[i+j+mid]*w; 83                 x[i+j]=u+v;x[i+j+mid]=u-v; 84                 w=w*wn; 85             } 86         } 87     } 88     if(flag==-1)for0(i,n-1)x[i].x/=n; 89 }             90  91 int main() 92  93 { 94  95     freopen("input.txt","r",stdin); 96  97     freopen("output.txt","w",stdout); 98  99     n=read();100     for1(i,n)num[i]=read(),mx=max(num[i],mx),r[num[i]]++;101     mx++;mx=mx*2-1;m=1;102     while(m<=mx)m<<=1,len++;mx=m;103     for0(i,mx-1)104     {105         int x=i,y=0;106         for1(j,len)y<<=1,y|=x&1,x>>=1;107         rev[i]=y;108     }109     size=2000;m=(n-1)/size+1;110     for1(i,m)st[i]=ed[i-1]+1,ed[i]=i*size;111     ed[m]=n;112     ll ans=0;113     for1(i,m)114     {115      for2(j,st[i],ed[i])r[num[j]]--;116      for0(j,mx-1)a[j]=(cp){l[j],0};117      for0(j,mx-1)b[j]=(cp){r[j],0};118      fft(a,mx,1);fft(b,mx,1);119      for0(j,mx-1)c[j]=a[j]*b[j];120      fft(c,mx,-1);121      for2(j,st[i],ed[i])ans+=(ll)(c[2*num[j]].x+0.5);122      for2(j,st[i],ed[i])123       {124         for2(k,st[i],j-1)if(2*num[j]-num[k]>=0)ans+=r[2*num[j]-num[k]];125         for2(k,j+1,ed[i])if(2*num[j]-num[k]>=0)ans+=l[2*num[j]-num[k]];126         l[num[j]]++;127       }128     }129     cout<<ans<<endl;130 131     return 0;132 133 }
View Code

一堆j打成i我也是醉了。。。

BZOJ3509: [CodeChef] COUNTARI


联系
我们