class BIT:
def __init__(self, n):
self.n = n
self.bit = [0]*(self.n+1)
def init(self, init_val):
for i, v in enumerate(init_val):
self.add(i, v)
def add(self, i, x):
i += 1 while i <= self.n:
self.bit[i] += x
i += (i & -i)
def sum(self, i, j):
return self._sum(j) - self._sum(i)
def _sum(self, i):
res = 0
while i > 0:
res += self.bit[i]
i -= i & (-i)
return res
def lower_bound(self, x):
s = 0
pos = 0
depth = self.n.bit_length()
v = 1 << depth
for i in range(depth, -1, -1):
k = pos + v
if k <= self.n and s + self.bit[k] < x:
s += self.bit[k]
pos += v
v >>= 1
return pos
def __str__(self): arr = [self.sum(i,i+1) for i in range(self.n)]
return str(arr)
n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]
A = [min(a, n-1) for a in A]
bit = BIT(n+5)
B = [[] for i in range(n)]
for i, a in enumerate(A):
bit.add(i, 1)
B[a].append(i)
ans = 0
for i, a in enumerate(A):
ans += bit.sum(0, a+1)
for j in B[i]:
bit.add(j, -1)
for i, a in enumerate(A):
if a >= i:
ans -= 1
ans //= 2
print(ans)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define int long long
#define ull unsigned long long
#define lowbit(i) ((i)&(-i))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 200;
int qpow(int a, int n) {
int ans = 1;
while (n) {
if (n & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return ans;
}
//int a[N];
class BIT{
public:
vector<int> c;
int sz;
BIT(int n):c(n+1){sz=n;}
void add(int pos,int k);
int query(int i);
};
void BIT::add(long long pos, long long k) {
while(pos<=sz){
c[pos]+=k;
pos+=lowbit(pos);
}
}
int BIT::query(long long i) {
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int a[N];
signed main() {
IOS
int n;
cin>>n;
BIT bit(n+1);
vector<vector<int>> g(n+1,vector<int>());
for(int i=1;i<=n;i++)
{
cin>>a[i];
g[min(a[i],n)].push_back(i);
bit.add(i,1);
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=bit.query(min(a[i],n));
for(auto j:g[i])
{
bit.add(j,-1);
}
// cout<<ans<<endl;
}
for(int i=1;i<=n;i++)
{
if(a[i]>=i)ans--;
}
cout<<ans/2<<endl;
return 0;
}1437A - Marketing Scheme | 1473B - String LCM |
1374A - Required Remainder | 1265E - Beautiful Mirrors |
1296A - Array with Odd Sum | 1385A - Three Pairwise Maximums |
911A - Nearest Minimums | 102B - Sum of Digits |
707A - Brain's Photos | 1331B - Limericks |
305B - Continued Fractions | 1165B - Polycarp Training |
1646C - Factorials and Powers of Two | 596A - Wilbur and Swimming Pool |
1462B - Last Year's Substring | 1608B - Build the Permutation |
1505A - Is it rated - 2 | 169A - Chores |
765A - Neverending competitions | 1303A - Erasing Zeroes |
1005B - Delete from the Left | 94A - Restoring Password |
1529B - Sifid and Strange Subsequences | 1455C - Ping-pong |
1644C - Increase Subarray Sums | 1433A - Boring Apartments |
1428B - Belted Rooms | 519B - A and B and Compilation Errors |
1152B - Neko Performs Cat Furrier Transform | 1411A - In-game Chat |