Problem:
 Score : 600 points    Problem Statement We have a set S of N points in a two-dimensional plane. The coordinates of the i -th point are (x_i, y_i) . The N points have distinct x -coordinates and distinct y -coordinates.  For a non-empty subset T of S , let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T . More formally, we define f(T) as follows:   f(T) := (the number of integers i  (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d , where a , b , c , and d are the minimum x -coordinate, the maximum x -coordinate, the minimum y -coordinate, and the maximum y -coordinate of the points in T )   Find the sum of f(T) over all non-empty subset T of S . Since it can be enormous, print the sum modulo 998244353 .      Constraints  1 \leq N \leq 2 \times 10^5  -10^9 \leq x_i, y_i \leq 10^9  x_i \neq x_j (i \neq j)  y_i \neq y_j (i \neq j)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  :  x_N  y_N       Output Print the sum of f(T) over all non-empty subset T of S , modulo 998244353 .        Sample Input 1 3
-1 3
2 1
3 -2      Sample Output 1 13  Let the first, second, and third points be P_1 , P_2 , and P_3 , respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:   f(\{P_1\}) = 1  f(\{P_2\}) = 1  f(\{P_3\}) = 1  f(\{P_1, P_2\}) = 2  f(\{P_2, P_3\}) = 2  f(\{P_3, P_1\}) = 3  f(\{P_1, P_2, P_3\}) = 3   The sum of these is 13 .       Sample Input 2 4
1 4
2 1
3 3
4 2      Sample Output 2 34       Sample Input 3 10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6      Sample Output 3 7222  Be sure to print the sum modulo 998244353 .

Solution (Python):
import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
bit = Bit(n)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    a = bit.sum(y)
    b = i - a
    c = y - a - 1
    d = (n - i - 1) - c
    bit.add(y, 1)
    
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * (pb + pc - 1) % MOD
    tmp += (pb - 1) * (pc - 1) % MOD * pa * pd % MOD
    ans = (ans + tmp) % MOD
print(ans)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

from operator import itemgetter
import sys
input = sys.stdin.readline
mod = 998244353
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort(key=itemgetter(1))
for i in range(N):
    XY[i][1] = i
XY.sort(key=itemgetter(0))
bitL = Bit(N)
bitR = Bit(N)
L = []  
R = [0]*N  
for _, y in XY:
    L.append(bitL.sum(y))
    bitL.add(y, 1)
for i, (_, y) in zip(range(N-1,-1,-1), XY[::-1]):
    R[i] = bitR.sum(y)
    bitR.add(y, 1)
ans = N * pow(2, N-1, mod) % mod

for i, (ld, rd) in enumerate(zip(L, R)):
    lu = i - ld
    ru = N - 1 - i - rd
    
    p_lu, p_ld, p_ru, p_rd = pow(2,lu,mod), pow(2,ld,mod), pow(2,ru,mod), pow(2,rd,mod)
    d = p_ru*p_ld*(p_lu-1)*(p_rd-1)\
           + p_lu*p_rd*(p_ru-1)*(p_ld-1)\
           - (p_lu-1)*(p_rd-1)*(p_ru-1)*(p_ld-1)
    
    ans = (ans + d) % mod



print(ans)

Solution (Python):
from bisect import bisect_left as bl
N = int(input())
P = 998244353
NN = 18
XX = [0] * (2**(NN+1)-1)
pow2 = [1]
for _ in range(1, 202020):
    pow2.append(pow2[-1]*2%P)

def addvalue(j):
    i = 2**NN + j - 1
    while i >= 0:
        XX[i] += 1
        i = (i-1) // 2

def rangesum(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    s = 0
    while l < r:
        if l%2:
            s += XX[l-1]
            l += 1
        if r%2:
            r -= 1
            s += XX[r-1]
        l >>= 1
        r >>= 1
    return s

X = []
Y = []
XY = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    XY.append((x, y))

X = sorted(X)
Y = sorted(Y)
XY = sorted(XY, key = lambda x: x[1])

DX = {}
for i in range(N):
    DX[X[i]] = i

ans = 0
U = 0
for x, y in XY:
    a = rangesum(0, DX[x])
    L = bl(X, x)
    b = U-a
    d = L-a
    c = N-a-b-d-1
    ans = (ans + pow2[N] - (pow2[a+b] + pow2[b+c] + pow2[c+d] + pow2[d+a] - pow2[a] - pow2[b] - pow2[c] - pow2[d] + 1)) % P
    U += 1
    addvalue(DX[x])
    
print(ans)

Solution (Python):
import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
f_bit = Bit(n)
b_bit = Bit(n)
for i in range(1, n + 1):
    b_bit.add(i, 1)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    b_bit.add(y, -1)
    a = f_bit.sum(y)
    b = i - a
    c = b_bit.sum(y)
    d = (n - i - 1) - c
    f_bit.add(y, 1)
    
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * pb * pc
    tmp += (pb - 1) * (pc - 1) * pa * pd
    tmp -= (pa - 1) * (pb - 1) * (pc - 1) * (pd - 1)
    ans = (ans + tmp) % MOD
print(ans)

Solution (Python):
import sys
from operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()

co = []
for i in range(n):
    co.append(na())

co.sort(key=itemgetter(1))
for i in range(n):
    co[i][1] = i


ft = [0] * (n + 5)

co.sort(key=itemgetter(0), reverse=True)

ups = [0] * n
downs = [0] * n

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

for i in range(n):
    c = co[i]
    downs[n-1-i] = sumfenwick(ft, c[1])
    ups[n-1-i] = i - downs[n-1-i]
    addfenwick(ft, c[1], 1)

ft = [0] * (n+5)
co = co[::-1]

mod = 998244353
ps = [0] * (n+5)
ps[0] = 1
for i in range(1, n+4):
    ps[i] = ps[i-1] * 2 % mod

ans = 0
for i in range(n):
    c = co[i]
    d = sumfenwick(ft, c[1])
    u = i - d

    
    ans += (ps[d]-1) * (ps[ups[i]]-1) * ps[u+downs[i]]
    ans += (ps[u]-1) * (ps[downs[i]]-1) * ps[d+ups[i]]
    ans -= (ps[d]-1) * (ps[ups[i]]-1) * (ps[downs[i]]-1) * (ps[u]-1)
    ans += ps[n-1]
    addfenwick(ft, c[1], 1)

ans %= mod
if ans < 0:
    ans += mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort() 
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    
    
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)