E. GukiZ and GukiZiana
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/551/problem/E
Description
Professor GukiZ was playing with arrays again and accidentally discovered new function, which he called GukiZiana. For given array a, indexed with integers from 1 to n, and number y, GukiZiana(a, y) represents maximum value of j - i, such that aj = ai = y. If there is no y as an element in a, then GukiZiana(a, y) is equal to - 1. GukiZ also prepared a problem for you. This time, you have two types of queries:
First type has form 1 l r x and asks you to increase values of all ai such that l ≤ i ≤ r by the non-negative integer x.
Second type has form 2 y and asks you to find value of GukiZiana(a, y).
For each query of type 2, print the answer and make GukiZ happy!
First type has form 1 l r x and asks you to increase values of all ai such that l ≤ i ≤ r by the non-negative integer x.
Second type has form 2 y and asks you to find value of GukiZiana(a, y).
For each query of type 2, print the answer and make GukiZ happy!
Input
The first line contains two integers n, q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104), size of array a, and the number of queries.
The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), forming an array a.
Each of next q lines contain either four or two numbers, as described in statement:
If line starts with 1, then the query looks like 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109), first type query.
If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 109), second type query.
The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), forming an array a.
Each of next q lines contain either four or two numbers, as described in statement:
If line starts with 1, then the query looks like 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109), first type query.
If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 109), second type query.
Output
For each query of type 2, print the value of GukiZiana(a, y), for y value for that query.
Sample Input
4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3
Sample Output
2
HINT
题意
一堆数，俩操作
[l,r]区间的数都加 v
查询最大的j-i,要求满足a[j]=a[i]=v
题解：
时间10s，这就是明摆着告诉我们这道题是分块，然后我们就分块乱搞就好了……
二分写挂的都是傻逼（没错就是我！
代码：
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 2000001 #define mod 10007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** ll n,q,m,block; ll a[1000001],b[1000001],pos[1000001],add[1000001]; void reset(ll x) { ll l=(x-1)*block+1,r=min(x*block,n); for(ll i=l;i<=r;i++) b[i]=a[i]; sort(b+l,b+r+1); } ll find(ll x,ll v) { ll l=(x-1)*block+1,r=min(x*block,n); ll last=r; while(l<r) { ll mid=(l+r)>>1; if(b[mid]<v)l=mid+1; else r=mid; if(b[mid]==v) return 1; } if(b[l]==v||b[r]==v) return 1; return 0; } void update(ll x,ll y,ll v) { if(pos[x]==pos[y]) { for(int i=x;i<=y;i++)a[i]=a[i]+v; } else { for(int i=x;i<=pos[x]*block;i++)a[i]=a[i]+v; for(int i=(pos[y]-1)*block+1;i<=y;i++)a[i]=a[i]+v; } reset(pos[x]);reset(pos[y]); for(int i=pos[x]+1;i<pos[y];i++) add[i]+=v; } ll query(ll x,ll y,ll v) { ll sum=0; if(pos[x]==pos[y]) { for(int i=x;i<=y;i++)if(a[i]+add[pos[i]]==v)sum++; } else { for(int i=x;i<=pos[x]*block;i++) if(a[i]+add[pos[i]]==v)sum++; for(int i=(pos[y]-1)*block+1;i<=y;i++) if(a[i]+add[pos[i]]==v)sum++; } for(int i=pos[x]+1;i<pos[y];i++) sum+=find(i,v-add[i]); //cout<<sum<<endl; return sum; } ll deall(ll x,ll y,ll v) { ll sum=0; if(pos[x]==pos[y]) { for(int i=x;i<=y;i++)if(a[i]+add[pos[i]]==v)return i; } else { for(int i=x;i<=pos[x]*block;i++) if(a[i]+add[pos[i]]==v)return i; for(int i=pos[x]+1;i<pos[y];i++) { int d=find(i,v-add[i]); if(d>0) { for(int j=i*block-block+1;j<=i*block;j++) if(a[j]+add[pos[j]]==v) return j; } } for(int i=(pos[y]-1)*block+1;i<=y;i++) if(a[i]+add[pos[i]]==v)return i; } } ll dealr(ll x,ll y,ll v) { ll sum=0; if(pos[x]==pos[y]) { for(int i=y;i>=x;i--)if(a[i]+add[pos[i]]==v)return i; } else { for(int i=y;i>=(pos[y]-1)*block+1;i--) if(a[i]+add[pos[i]]==v) return i; for(int i=pos[y];i>=pos[x]+1;i--) { int d=find(i,v-add[i]); if(d>0) { for(int j=i*block;j>=i*block-block;j--) if(a[j]+add[pos[j]]==v) return j; } } for(int i=pos[x]*block;i>=x;i--) if(a[i]+add[pos[i]]==v)return i; } } int ask(ll cc) { int aa=query(1,n,cc); if(aa==0) return -1; return dealr(1,n,cc)-deall(1,n,cc); } int main() { //test; n=read(),q=read(); block=int(sqrt(n)); for(int i=1;i<=n;i++) { a[i]=read(); pos[i]=(i-1)/block+1; b[i]=a[i]; } int x,y,v,ch; if(n%block)m=n/block+1; else m=n/block; for(int i=1;i<=m;i++)reset(i); for(int i=1;i<=q;i++) { ch=read(); if(ch==1) { x=read(),y=read(),v=read(); update(x,y,v); } else { int p; p=read(); printf("%d ",ask(p)); } } return 0; }