8.8考试总结
T1
简单的分块模版，原题为守墓人。
T2
容易想到前缀和，但是前缀和的复杂度为
想到树状数组也可以实现相同效果，且复杂度
T3
与昨天的第三天相似，知识这次用的是树状数组。
维护两个树状数组，之后直接求贡献即可。
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
// #define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
int n , k , f ;
int len , res ;
ll a[kMaxN] , c[kMaxN][2] ;
int id[kMaxN] ;
int lowbit(int x)
{
return (x & (-x)) ;
}
ll query(int x , int te)
{
ll sum = 0 ;
while(x)
{
sum += c[x][te] ;
x -= lowbit(x) ;
}
return sum ;
}
void update(int x , ll v , int k , int te)
{
while(x <= k)
{
c[x][te] += v ;
x += lowbit(x) ;
}
}
ll cal(int x)
{
if(x < 0) return 0 ;
return x * query(x , 0) - query(x , 1) ;
}
void work()
{
cin >> n >> k ;
for( int i(1) ; i <= n ; ++i )
{
cin >> a[i] ;
update(i , a[i] , n , 0) ;
update(i , 1ll * a[i] * (i - 1) , n , 1) ;
}
cin >> f ;
while(f--)
{
int op ;
cin >> op ;
if(op == 1)
{
for( int i(1) ; i <= k ; ++i )
{
cin >> id[i] ;
}
int tmp = a[id[1]] ;
for( int i = 1 ; i < k ; i++ )
{
update(id[i] , a[id[i + 1]] - a[id[i]] , n , 0) ;
update(id[i] , 1ll * (a[id[i + 1]] - a[id[i]]) * (id[i] - 1) , n , 1) ;
a[id[i]] = a[id[i + 1]] ;
}
update(id[k] , tmp - a[id[k]] , n , 0) ;
update(id[k] , 1ll * (tmp - a[id[k]]) * (id[k] - 1) , n , 1) ;
a[id[k]] = tmp ;
}
else
{
int l , r , m ;
cin >> l >> r >> m ;
cout << cal(r) - cal(l + m - 2) - (cal(r - m) - cal(l - 2)) << "\n" ;
}
}
}
signed main()
{
// freopen(".in" , "r" , stdin) ;
// freopen(".out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}
T4
用容斥原理，把一个询问分成
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
// #define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 5e4 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
int n , f ;
int len , res ;
int a[kMaxN] , cnt[kMaxN] , buc[kMaxN] , ans[kMaxN] ;
struct node
{
int l , r , id , val ;
}Node[kMaxN * 4] ;
bool cmp(node x , node y)
{
if(x.l / len == y.l / len)
{
if((x.l / len) % 2) return x.r < y.r ;
return x.r > y.r ;
}
return x.l < y.l ;
}
void ADD1(int x)
{
cnt[a[x]]++ ;
res += buc[a[x]] ;
}
void SUB1(int x)
{
cnt[a[x]]-- ;
res -= buc[a[x]] ;
}
void ADD2(int x)
{
buc[a[x]]++ ;
res += cnt[a[x]] ;
}
void SUB2(int x)
{
buc[a[x]]-- ;
res -= cnt[a[x]] ;
}
void work()
{
cin >> n ;
len = sqrt(n) ;
for( int i(1) ; i <= n ; ++i )
{
cin >> a[i] ;
}
cin >> f ;
int op = 0 ;
for( int i(1) ; i <= f ; ++i )
{
int l1 , r1 , l2 , r2 ;
cin >> l1 >> r1 >> l2 >> r2 ;
Node[++op] = {r1 , r2 , i , 1} ;
Node[++op] = {r1 , l2 - 1 , i , -1} ;
Node[++op] = {l1 - 1 , r2 , i , -1} ;
Node[++op] = {l1 - 1 , l2 - 1 , i , 1} ;
}
sort(Node + 1 , Node + op + 1 , cmp) ;
int l = 1 , r = 0 ;
for( int i(1) ; i <= op ; ++i )
{
while(l < Node[i].l) ADD1(++l) ;
while(l > Node[i].l) SUB1(l--) ;
while(r < Node[i].r) ADD2(++r) ;
while(r > Node[i].r) SUB2(r--) ;
ans[Node[i].id] += Node[i].val * res ;
}
for( int i(1) ; i <= f ; ++i ) cout << ans[i] << "\n" ;
}
signed main()
{
// freopen(".in" , "r" , stdin) ;
// freopen(".out" , "w" , stdout) ;
// ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}