BZOJ3509: [CodeChef] COUNTARI

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

题解：

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我也是醉了。。。