 # FIXPTS - Editorial

Editorialist: Nishank Suresh

Cakewalk

None

# PROBLEM:

Given an array A, find the sum of the number of fixed points over all subarrays [A_L, A_{L+1}, \dots, A_R], where a fixed point of an array B is an index i such that B_i = i.

# QUICK EXPLANATION:

The answer is the sum of N-i+1 over all indices 1\leq i\leq N such that A_i \leq i.

# EXPLANATION:

Counting the number of fixed points for each subarray and summing them up is too slow, so we instead employ a trick commonly used in such counting problems - we instead look at each index and try to figure out how many subarrays it is a fixed point of, and then sum this over all possible indices.

Fix some index 1\leq i\leq N. When is this index a fixed point of a subarray [L, R]?
Of course, the very first condition which needs to be satisfied is that i needs to belong to the subarray in the first place, i.e, L\leq i\leq R.

Further, the condition of i being a fixed point tells us that A_i = i-L+1.
Rewriting this condition, we obtain L = i - A_i + 1 - in other words, there is exactly one choice of L given that i is fixed.
However, we must also have L\geq 1, so i - A_i + 1\geq 1 \iff i\geq A_i.

The choice of R doesn’t affect i being a fixed point, so any R such that R\geq i works, and there are N-i+1 of these.

Our final answer is thus simply the sum of N-i+1 over all indices 1\leq i\leq N such that A_i \leq i.

\mathcal{O}(N)

# CODE:

Setter (C++)
#include<bits/stdc++.h>
using namespace std;

void solve() {
int n ; cin >> n;
long long ans = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i >= x) ans += (n - i + 1);
}
cout << ans << '\n';
}

signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; i++) solve();
return 0;
}

Tester (Kotlin)
import java.io.BufferedInputStream

fun main(omkar: Array<String>) {
val jin = FastScanner()
var nSum = 0
repeat(jin.nextInt(1000)) {
val n = jin.nextInt(100000)
nSum += n
if (nSum > 500000) {
throw InvalidInputException("constraint on sum n violated")
}
for (j in 1..n) {
val x = jin.nextInt(n, j == n)
if (x <= j) {
answer += (n - j + 1).toLong()
}
}
}
jin.endOfInput()
}

class InvalidInputException(message: String): Exception(message)

class FastScanner {
private val BS = 1 shl 16
private val NC = 0.toChar()
private val buf = ByteArray(BS)
private var bId = 0
private var size = 0
private var c = NC
private var in: BufferedInputStream? = null
private val validation: Boolean

constructor(validation: Boolean) {
this.validation = validation
in = BufferedInputStream(System.in, BS)
}

constructor() : this(true)

private val char: Char
private get() {
while (bId == size) {
size = try {
in!!.read(buf)
} catch (e: Exception) {
return NC
}
if (size == -1) return NC
bId = 0
}
return buf[bId++].toChar()
}

fun validationFail(message: String) {
if (validation) {
throw InvalidInputException(message)
}
}

fun endOfInput() {
if (char != NC) {
validationFail("excessive input")
}
if (validation) {
System.err.println("input validated")
}
}

fun nextInt(from: Int, to: Int, endsLine: Boolean = true) = nextLong(from.toLong(), to.toLong(), endsLine).toInt()

fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)

fun nextLong(endsLine: Boolean): Long {
var neg = false
c = char
if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
validationFail("found character other than digit, negative sign, space, and newline, character code = ${c.toInt()}") } if (c == '-') { neg = true c = char } var res = 0L while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0').toLong() c = char } if (endsLine) { if (c != '\n') { validationFail("found character other than newline, character code =${c.toInt()}")
}
} else {
if (c != ' ') {
validationFail("found character other than space, character code = ${c.toInt()}") } } return if (neg) -res else res } fun nextLong(from: Long, to: Long, endsLine: Boolean = true): Long { val res = nextLong(endsLine) if (res !in from..to) { validationFail("$res not in range $from..$to")
}
return res
}

fun nextLong(to: Long, endsLine: Boolean = true) = nextLong(1L, to, endsLine)
}

Editorialist (Python)
import sys

can anybody can tell me whats the problem in my code. As my whole logic is same as that of the setter code#include <iostream> using namespace std; int main () { ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); int t ; cin>>t; while(t--) { int count=0,i,j,n; cin>>n; int arr[n+1]; for(i=1;i<=n;i++) { cin>>arr[i]; if(i-arr[i]>=0) count+=n-i+1; } cout <<count<<"\n"; } return 0; }