Cách của mình, khá trâu, và mình nghĩ khá dễ chết 2 subtask cuối:
Có 1 nhận xét là a[i]<=1000, tức là khi biểu diễn sang nhị phân thì độ dài tối đa của a[i] khi biểu diễn sang hệ nhị phân là 10 -> kết quả của các phép tính (x op y) (với op là các phép and, or, xor) sẽ có kết quả không quá 1023.
Dùng 2 vector 2 chiều AND và OR để lưu lại kết quả:
Khởi tạo i, j: \(AND[a[i]\ and\ a[j]].push\_back(j)\ (i<j \leq n-2)\)
OR[i][] lưu lại các chỉ số j sao cho \(\forall n-1\geq j > AND[k][p]:a[j]\ or\ OR[i][AND[k][p]] = i\ (p \leq AND[k].size())\) (vì sao \( n-2\geq p\) thì các bạn tự hiểu nhé)
Cuối cùng, đếm xem có bao nhiêu chỉ số j mà \(i\ xor\ j \in [l,r]\ (OR[i][k]<j \leq n;\ k \leq OR[i].size())\)
Độ phức tạp là \(O(1024*n^2)\), nhưng vì n<=4000 nên rất dễ TLE.
Có thể đặt cận để giảm thời gian chạy xuống 1 chút :3
Còn 1 cách sol chuẩn (thì phải) là dp 3 chiều, nhưng minh chưa code :3