Problem E. GukiZ and GukiZiana
Solution：
先分成N=sqrt（n）块，然后对这N块进行排序。
利用二分查找确定最前面和最后面的位置。
#include <bits/stdc++.h> using namespace std; typedef long long ll;
vector<int> s[];
ll add[], a[], pos[];
ll n, q, bk, N; bool cmp( int x, int y )
{
if( a[x] == a[y] ) return x < y;
return a[x] < a[y];
} inline void modify( ll l, ll r, ll x )
{
int k = pos[l], t = pos[r]; if( k == t ) {
for( ll i = l; i <= r; ++i )
a[i] += x;
sort( s[k].begin(), s[k].end(), cmp );
return ;
} for( ll i = k + ( pos[l - ] == k ); i <= t - ( pos[r + ] == t ) ; ++i )
add[i] += x; if( pos[l - ] == k ) {
for( ll i = l; pos[i] == k; ++i ) {
a[i] += x;
}
sort( s[k].begin(), s[k].end(), cmp );
} if( pos[r + ] == t ) {
for( ll i = r; pos[i] == t; --i ) {
a[i] += x;
}
sort( s[t].begin(), s[t].end(), cmp );
}
} inline ll query( ll x )
{
int l = -, r = -, i;
for( i = ; i <= N; ++i ) {
a[] = x - add[i];
auto it = lower_bound( s[i].begin(), s[i].end(), , cmp );
if( it == s[i].end() ) continue;
if( a[*it] + add[i] == x ) {
l = *it;
break;
}
} if( l == - ) return l;
for( int j = N; j >= i; --j ) {
a[n + ] = x - add[j];
auto it = lower_bound( s[j].begin(), s[j].end(), n + , cmp );
if( it == s[j].begin() ) continue;
it--;
if( a[*it] + add[j] == x ) {
r = *it;
break;
}
}
return r - l;
} int main()
{
ios::sync_with_stdio( );
cin >> n >> q;
bk = ceil( sqrt( .*n ) + 0.005 );
for( int i = ; i <= n; ++i ) {
cin >> a[i];
pos[i] = ( i - ) / bk + ;
s[pos[i]].push_back( i );
}
N = ( n - ) / bk + ;
for( int i = ; i <= N; ++i ) {
sort( s[i].begin(), s[i].end(), cmp );
}
ll cmd, l, r, x;
for( int i = ; i <= q; ++i ) {
cin >> cmd;
if( cmd == ) {
cin >> l >> r >> x;
modify( l, r, x );
} else {
cin >> x;
cout << query( x ) << "\n";
}
}
}