Hướng dẫn cho AtCoder ABC231F - Hai người hay ghen
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Hai điều kiện cho một cặp quà
Nếu Takahashi nhận loại \(i\), Aoki nhận loại \(j\), hai người không ghen khi và chỉ khi:
Cần đếm cặp có thứ tự \((i,j)\), bao gồm \(i=j\). Hai loại có cùng cặp \((A,B)\) vẫn là hai lựa chọn khác nhau.
Sắp xếp và đếm bằng Fenwick
Sắp các loại theo \(A\) tăng; nếu \(A\) bằng nhau, sắp \(B\) giảm. Nén các giá trị \(B\), rồi dùng Fenwick lưu số loại đã xét theo \(B\).
Gộp những loại có cùng cặp \((A,B)\) thành một nhóm, gọi kích thước nhóm là \(c\). Thêm cả \(c\) loại vào Fenwick trước. Nếu tổng số loại đã thêm là seen, số lựa chọn \(j\) có \(B_j\ge B\) bằng seen - prefix(rank(B)-1). Nhóm hiện tại đóng góp:
Nhờ thêm trước khi hỏi, \(c\) lựa chọn trong nhóm có thể ghép với cả \(c\) lựa chọn của chính nhóm, cho \(c^2\) cách. Nếu thêm từng loại một rồi hỏi, những cặp giống hệt sẽ chỉ được tính theo một chiều.
Vì sao thứ tự này đếm đủ và không đếm thừa?
Với một nhóm đang xét, mọi nhóm đã thêm có \(A_j\le A_i\). Khi \(A\) bằng nhau, nhóm có \(B\) lớn hơn đứng trước, nên mọi lựa chọn hợp lệ có cùng \(A\) đã có trong Fenwick. Truy vấn chỉ lấy \(B_j\ge B_i\), đúng điều kiện còn lại. Mỗi nhóm được dùng đúng một lần làm lựa chọn cho Takahashi, nên mỗi cặp có thứ tự được tính đúng một lần.
Thời gian \(O(N\log N)\) và bộ nhớ \(O(N)\). Đáp án có thể bằng \(N^2=4\cdot10^{10}\), nên C++ dùng long long. Không lấy modulo.
Mã tham khảo
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int n;if(!(cin>>n))return 0;
vector<int>A(n),B(n),ys;for(int&x:A)cin>>x;for(int&x:B)cin>>x;
vector<pair<int,int>> points(n);for(int i=0;i<n;++i)points[i]={A[i],-B[i]};
sort(points.begin(),points.end());ys=B;sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end());
vector<int>bit(ys.size()+1);long long answer=0,seen=0;
for(int i=0;i<n;){
int j=i+1;while(j<n&&points[j]==points[i])++j;
long long count=j-i;int b=-points[i].second;
int rank=lower_bound(ys.begin(),ys.end(),b)-ys.begin()+1;
for(int p=rank;p<(int)bit.size();p+=p&-p)bit[p]+=count;
seen+=count;long long lower=0;
for(int p=rank-1;p;p-=p&-p)lower+=bit[p];
answer+=count*(seen-lower);i=j;
}
cout<<answer<<'\n';
}
import sys
def solve(data):
n = data[0]
A, B = data[1:n + 1], data[n + 1:2 * n + 1]
points = sorted(zip(A, (-b for b in B)))
ys = sorted(set(B))
ranks = {value: i + 1 for i, value in enumerate(ys)}
bit = [0] * (len(ys) + 1)
seen = answer = i = 0
while i < n:
j = i + 1
while j < n and points[j] == points[i]:
j += 1
count = j - i
rank = ranks[-points[i][1]]
p = rank
while p < len(bit):
bit[p] += count
p += p & -p
seen += count
lower, p = 0, rank - 1
while p:
lower += bit[p]
p -= p & -p
answer += count * (seen - lower)
i = j
return str(answer) + '\n'
if __name__ == '__main__':
sys.stdout.write(solve(list(map(int, sys.stdin.buffer.read().split()))))
Bình luận