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):
def main():
    from sys import stdin
    input = stdin.readline
    mod = 998244353
    n = int(input())
    xy = [list(map(int, input().split())) for _ in [0]*n]
    ans = 0
    pow_2 = [1]
    j = 1
    for i in range(n):
        j = j*2 % mod
        pow_2.append(j)
    p2 = pow_2[n-1]

    xy.sort(key=lambda x: x[1])
    xy = [(x, i+1) for i, (x, y) in enumerate(xy)]
    xy.sort()

    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(self.n))-3)
            self.bit = [0]*(self.n+1)
            self.allsum = 0

        
        def all_plus(self):
            self.bit = [0]+[i & (-i) for i in range(1, self.n+1)]
            self.allsum = self.n

        
        def add(self, i, v):
            x = i
            self.allsum += v
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

    bit_left = BIT(n)
    bit_right = BIT(n)
    bit_right.all_plus()

    for i, (x, y) in enumerate(xy):
        bit_right.add(y, -1)
        A = bit_left.sum(y)
        B = i-A
        C = bit_right.sum(y)
        D = n-i-1-C
        bit_left.add(y, 1)
        ans += (pow_2[A]-1)*(pow_2[D]-1)*(pow_2[B+C])
        ans += (pow_2[B]-1)*(pow_2[C]-1)*(pow_2[A+D])
        ans -= (pow_2[B]-1)*(pow_2[C]-1)*(pow_2[A]-1)*(pow_2[D]-1)
        ans += p2
        ans = ans % mod
    print(ans)


main()

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [0] * (2 * self.N0)

	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.data[2 * k + 1] + self.data[2 * k + 2]

	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = 0
		while L < R:
			if R & 1:
				R -= 1
				m += self.data[R - 1]
			if L & 1:
				m += self.data[L - 1]
				L += 1
			L >>= 1; R >>= 1

		return m


def main():
	N = int(input())
	XY = [None] * N
	X = [None] * N
	Y = [None] * N
	for i in range(N):
		x, y = getlist()
		XY[i] = [x, y]
		X[i] = x; Y[i] = y

	
	X.sort(); Y.sort()
	Dx = defaultdict(int)
	Dy = defaultdict(int)
	for i in range(N):
		Dx[X[i]] = i
		Dy[Y[i]] = i

	for i in range(N):
		XY[i] = Dx[XY[i][0]], Dy[XY[i][1]]

	XY.sort(key=lambda x: x[0])
	YY = [XY[i][1] for i in range(N)]
	
	
	
	Segleft = SegmentTree(N)
	Segright = SegmentTree(N)

	
	ans = pow(2, N - 1, con) * N
	ans %= con

	yLU = [0] * N
	yLD = [0] * N
	yRU = [0] * N
	yRD = [0] * N

	
	Segleft.update(YY[0], 1)

	for i in range(1, N - 1):
		y = YY[i]
		yLD[i] = Segleft.query(0, y)
		yLU[i] = Segleft.query(y, N - 1)
		Segleft.update(y, 1)

	
	Segright.update(YY[N - 1], 1)

	for i in range(N - 2, 0, -1):
		y = YY[i]
		yRD[i] = Segright.query(0, y)
		yRU[i] = Segright.query(y, N - 1)
		Segright.update(y, 1)

	
	
	
	

	for i in range(1, N - 1):
		lu = yLU[i]; ru = yRU[i]
		ld = yLD[i]; rd = yRD[i]
		a = pow(2, lu, con)
		b = pow(2, ru, con)
		c = pow(2, ld, con)
		d = pow(2, rd, con)
		if rd != 0 and lu != 0:
			ans += (d - 1) * (a - 1) * b * c
		if ld != 0 and ru != 0:
			ans += (c - 1) * (b - 1) * a * d
		
		if rd != 0 and lu != 0 and ld != 0 and ru != 0:
			ans -= (a - 1) * (b - 1) * (c - 1) * (d - 1)
		ans %= con

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys

input=sys.stdin.readline

N=int(input())
p=[]
for i in range(N):
    x,y=map(int,input().split())
    p.append([x,y])
mod=998244353

pow=[1]
for i in range(N):
    pow.append((pow[-1]*2)%mod)

p.sort(key=lambda x:x[1])
for i in range(N):
    p[i][1]=i+1


data=[[0 for i in range(4)] for i in range(N)]

n=N
BIT = [0]*(n+1)


def BIT_query(idx):
    if idx==0:
        return 0
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

p.sort()
for i in range(N):
    x,y=p[i]
    a,b=i,BIT_query(y)
    data[i][0]=a-b
    data[i][3]=b
    BIT_update(y,1)

BIT=[0]*(n+1)
for i in range(N-1,-1,-1):
    x,y=p[i]
    a,b=N-1-i,BIT_query(y)
    data[i][1]=a-b
    data[i][2]=b
    BIT_update(y,1)

ans=0
for i in range(N):
    ban=0
    for j in range(4):
        ban+=(pow[data[i][j]]-1)*pow[data[i][j-1]]
        ban%=mod
    ans+=pow[N]-ban-1
    ans%=mod
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
mod=998244353
from operator import itemgetter
l.sort(key=itemgetter(1))
for i in range(n):
    l[i][1]=i
l.sort(key=itemgetter(0))

No=2
while No<=n:
    No*=2
tree=[0]*(2*No)

def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
pow2=[1 for i in range(n+2)]
t=2
for i in range(1,n+2):
    pow2[i]=t
    t*=2
    t%=mod
ans=0
for x,y in l:
    lu=query(y,n)
    ld=query(0,y)
    ru=n-1-y-lu
    rd=y-ld
    ans+=pow2[n-1]+(pow2[lu]-1)*(pow2[rd]-1)%mod*(pow2[ru]+pow2[ld]-1+(pow2[ld]-1)*(pow2[ru]-1))%mod+(pow2[ld]-1)*(pow2[ru]-1)%mod*(pow2[rd]+pow2[lu]-1)%mod
    ans%=mod
    add(y,1)
print(ans)

Solution (Python):
MOD = 998244353
import bisect
import sys
input = sys.stdin.readline
N = int(input())
P = [list(map(int,input().split())) for i in [0]*N]

class SegmentTree:
    def __init__(self,data):
        N = len(data)
        self.l = 2**((N-1).bit_length())
        self.data = [0]*self.l + data + [0]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = self.data[2*i] + self.data[2*i+1]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.data[2*i] + self.data[2*i+1]
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = 0
        while j-i > 0:
            if i & 1:
                s += self.data[i]
                i += 1
            if j & 1:
                s += self.data[j-1]
                j -= 1
            i = i//2
            j = j//2
        return s

X,Y = map(list,zip(*P))
X.sort()
Y.sort()
compY = {y:cy for cy,y in enumerate(Y)}
Psorted = sorted(P)
compP = [[n,compY[y]] for n,(_,y) in enumerate(Psorted)]

n1s = []
seg = SegmentTree([0]*N)
for _,y in compP[::-1]:
    n1s.append(seg.get(y,N))
    seg.set(y,1)
n1s = n1s[::-1]

pows = [1]
for i in range(1,N):
    pows.append((pows[-1]*2) % MOD)

ans = (-4*sum(pows)- N + N * pow(2,N,MOD)) % MOD

for n,(x,y) in enumerate(Psorted):
    lower = bisect.bisect_left(Y,y)
    upper = N-1-lower
    left = n
    right = N-n-1
    n1 = n1s[n]
    n2 = upper - n1
    n3 = left - n2
    n4 = right - n1
    ans += pows[n1] + pows[n2] + pows[n3] + pows[n4]
    ans %= MOD

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
input = sys.stdin.readline
from collections import defaultdict
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
dcy = defaultdict(int)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yls = list(yls)
for i in range(n):
  dcy[yls[i]] = i
yls.sort()
yind = [0 for i in range(n)]
for i in range(n):
  ind = dcy[yls[i]]
  yind[ind] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

Solution (Python):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class BinaryIndexedTree:
    
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    
    def add(self, _i, x):
        i = _i
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def sum(self, _i):
        i = _i
        res = 0
        while i:
            res += self.data[i]
            i -= i & -i
        return res
    
    def bisect_left(self, _w):
        w = _w
        if w <= 0:
            return 0
        i = 0
        k = 1 << (self.n.bit_length() - 1)
        while 0 < k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k = k >> 1
        return i + 1


def solve():
    MOD = 998244353
    N = int(rl())
    xy = [[0, 0] for _ in range(N)]
    for i in range(N):
        xy[i][0], xy[i][1] = map(int, rl().split())
    
    compress = sorted(xy, key=itemgetter(1))
    for i in range(N):
        compress[i][1] = i
    compress.sort(key=itemgetter(0), reverse=True)
    
    bit = BinaryIndexedTree(N)
    ups = [0] * N
    downs = [0] * N
    for i in range(N):
        com = compress[i][1] + 1
        downs[N - 1 - i] = bit.sum(com)
        ups[N - 1 - i] = i - downs[N - 1 - i]
        bit.add(com, 1)
    
    bit = BinaryIndexedTree(N)
    compress = compress[::-1]
    
    pow_of_2 = [1]
    for _ in range(N):
        pow_of_2.append(pow_of_2[-1] * 2 % MOD)
    
    ans = 0
    for i in range(N):
        com = compress[i][1] + 1
        d = bit.sum(com)
        u = i - d
        ans = (ans + (pow_of_2[d] - 1) * (pow_of_2[ups[i]] - 1) * pow_of_2[u + downs[i]]) % MOD
        ans = (ans + (pow_of_2[u] - 1) * (pow_of_2[downs[i]] - 1) * pow_of_2[d + ups[i]]) % MOD
        ans = (ans - (pow_of_2[d] - 1) * (pow_of_2[ups[i]] - 1) * (pow_of_2[downs[i]] - 1) * (pow_of_2[u] - 1)) % MOD
        ans = (ans + pow_of_2[N - 1]) % MOD
        bit.add(com, 1)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
mod=998244353
from collections import defaultdict
DX=defaultdict(int)
DY=defaultdict(int)
XY,X,Y=[],[],[]
for _ in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append((x,y))
X.sort()
Y.sort()
XY.sort(key=lambda x:x[0])
for i,x in enumerate(X):
  DX[x]=i+1
for i,y in enumerate(Y):
  DY[y]=i+1
XY2=[]
for x,y in XY:
  XY2.append((DX[x],DY[y]))
A=[[0]*4 for _ in range(n)]

n_max=2*10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for i in range(n):
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][2]+=ct
  A[i][1]+=i-ct
  bitadd(BIT,y,1)

BIT=[0]*(2**nn)
BIT.insert(0,0)
for i in range(n)[::-1]:
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][3]+=ct
  A[i][0]+=(n-1-i)-ct
  bitadd(BIT,y,1)

P=[0]*n
P[0]=1
for i in range(1,n):
  P[i]=(P[i-1]*2)%mod
def f(x):
  return P[x]

ans=0
for a,b,c,d in A:
  ans+=2*f(a+b+c+d)-f(a+b)-f(b+c)-f(c+d)-f(d+a)+f(a)+f(b)+f(c)+f(d)-1
  ans%=mod
print(ans)

Solution (Python):
mod = 998244353

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

N, *XY = map(int, open(0).read().split())
X, Y = XY[::2], XY[1::2]

memo = {y: i for i, y in enumerate(sorted(Y))}
Y = [y for x, y in sorted(zip(X, map(memo.get, Y)), key=lambda p: p[0])]

P = [1]
for i in range(N):
    P.append(P[-1] * 2 % mod)

ans = P[N - 1] * N % mod
bit = BIT(N)
for i, y in enumerate(Y):
    bit.add(y + 1, 1)

    ld = bit.sum(y)
    lu = i - ld

    rd = y - ld
    ru = N - y - 1 - lu

    A, B, C, D = P[ru], P[lu], P[ld], P[rd]

    ans += ((C - 1) * (A - 1) % mod) * (B * D % mod) % mod
    ans += ((B - 1) * (D - 1) % mod) * (C * A % mod) % mod
    ans -= ((C - 1) * (A - 1) % mod) * ((D - 1) * (B - 1) % mod) % mod
    ans %= mod

print(ans)

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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

    def add(self, i, val):
        """i番目にvalを加える"""
        i += 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
      

n = int(input())
info = [tuple([i] + list(map(int, input().split()))) for i in range(n)]
MOD = 998244353

ans = [[0] * n for i in range(4)]

info = sorted(info, key = itemgetter(1))
to_ind = {x[2]: ind for ind, x in enumerate(sorted(info, key = itemgetter(2)))}

bit = BIT(n)
for j in range(n):
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[2][i]= tmp
    ans[3][i] = j - tmp
    bit.add(to_ind[y], 1)
    
bit = BIT(n)
for j in range(n)[::-1]:
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[1][i] = tmp
    ans[0][i] = n - j - 1 - tmp
    bit.add(to_ind[y], 1)

res = 0
pow2 = [1] * (n + 10)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2
    pow2[i + 1] %= MOD

ans = list(zip(*ans))
for a1, a2, b1, b2 in ans:
    res += (pow2[a1] - 1) * (pow2[b1] - 1) * (pow2[a2 + b2])
    res %= MOD
    res += (pow2[a2] - 1) * (pow2[b2] - 1) * (pow2[a1 + b1])
    res %= MOD
    res += pow2[n - 1]
    res -= (pow2[a1] - 1) * (pow2[a2] - 1) * (pow2[b1] - 1) * (pow2[b2] - 1)
    res %= MOD
print(res % MOD)

Solution (Python):
from bisect import bisect_right, bisect_left

class BITbisect():
    def __init__(self, InputProbNumbers):
        
        self.ind_to_co = [-10**18]
        self.co_to_ind = {}
        for ind, num in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind+1
        self.max = len(self.co_to_ind)
        self.data = [0]*(self.max+1)
    
    def __str__(self):
        retList = []
        for i in range(1, self.max+1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return "[" + ", ".join([str(a) for a in retList]) + "]"
    
    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < key:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max or key < 0:
            raise IndexError("BIT index out of range")
        return self.ind_to_co[ind+1]
    
    def __len__(self):
        return self._query_sum(self.max)
    
    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0
    
    
    
    def _query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    
    
    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i
    
    
    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The pushing number didnt initialized")
        self._add(self.co_to_ind[x], 1)
            
    
    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The deleting number didnt initialized")
        if self.count(x) <= 0:
            raise ValueError("The deleting number doesnt exist")
        self._add(self.co_to_ind[x], -1)

    
    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1)
    
    
    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    
    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i-1)

mod = 998244353

import sys
input = sys.stdin.readline

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

XY.sort()
D = [[0, 0, 0, 0] for _ in range(N)]
B1 = BITbisect(Ys)
for i, (x, y) in enumerate(XY):
    k = B1.bisect_left(y)
    D[i][0] = k
    D[i][1] = i-k
    B1.push(y)

B2 = BITbisect(Ys)
for i in reversed(range(N)):
    x, y = XY[i]
    k = B2.bisect_left(y)
    D[i][2] = k
    D[i][3] = (N-1-i)-k
    B2.push(y)

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

ans = 0
for i in range(N):
    a, b, c, d = D[i]
    p = N2[N] - 1 - (N2[a+b]+N2[b+d]+N2[d+c]+N2[c+a])%mod + (N2[a]+N2[b]+N2[c]+N2[d])%mod
    ans = (ans + p) % mod

print(ans)

Solution (Python):
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    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())
    X_raw = [0] * N
    Y_raw = [0] * N
    for i in range(N):
        x, y = map(int, input().split())
        X_raw[i] = x
        Y_raw[i] = y

    val2idx_X = {}
    val2idx_Y = {}
    for i in range(N):
        val2idx_X[X_raw[i]] = i
        val2idx_Y[Y_raw[i]] = i
    X_raw.sort()
    Y_raw.sort()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[val2idx_X[X_raw[i]]] = i+1
        Y[val2idx_Y[Y_raw[i]]] = i+1

    XY = [(x, y) for x, y in zip(X, Y)]
    XY.sort(key=itemgetter(0))

    bit_ul = Bit(N + 2)
    bit_ur = Bit(N+2)
    ul = []
    ur = []
    for x, y in XY:
        ul.append(bit_ul.sum(y))
        ur.append(bit_ur.sum(N+1) - bit_ur.sum(y))
        bit_ul.add(y, 1)
        bit_ur.add(y, 1)

    bit_dl = Bit(N + 2)
    bit_dr = Bit(N + 2)
    dl = []
    dr = []
    for x, y in reversed(XY):
        dl.append(bit_dl.sum(y))
        dr.append(bit_dr.sum(N + 1) - bit_dr.sum(y))
        bit_dl.add(y, 1)
        bit_dr.add(y, 1)
    dl.reverse()
    dr.reverse()

    ans = 0
    two_N = pow(2, N, mod) - 1
    for i in range(N):
        half = ((pow(2, ul[i]+ur[i], mod) + pow(2, dl[i]+dr[i], mod))%mod
                + (pow(2, ul[i]+dl[i], mod) + pow(2, ur[i]+dr[i], mod))%mod)%mod
        qu = ((pow(2, ul[i], mod) + pow(2, ur[i], mod))%mod
              +(pow(2, dl[i], mod) + pow(2, dr[i], mod))%mod)%mod
        ans = ((ans + two_N)%mod + (-half + qu)%mod)%mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

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

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)

Solution (Python):
from operator import itemgetter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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

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))
y = [xy[i][1] for i in range(N)]

mod = 998244353
p2 = [1]*(N+1)
for i in range(N):
    p2[i+1] = p2[i]*2%mod

bit1 = BIT(N)
bit2 = BIT(N)

for i in range(N):
    bit2.add(i,1)

ans = 0

for i in range(N):
    bit1.add(y[i],1)
    bit2.add(y[i],-1)
    n1 = bit1.sum(N-1)-bit1.sum(y[i])
    n2 = bit1.sum(y[i]-1)
    n3 = bit2.sum(N-1)-bit2.sum(y[i])
    n4 = bit2.sum(y[i]-1)
    ans += 1
    ans += (p2[n1]-1)+(p2[n2]-1)+(p2[n3]-1)+(p2[n4]-1)
    ans += (p2[n1]-1)*(p2[n2]-1)+(p2[n3]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)+(p2[n2]-1)*(p2[n4]-1)+2*(p2[n1]-1)*(p2[n4]-1)+2*(p2[n2]-1)*(p2[n3]-1)
    ans += 2*((p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)+(p2[n1]-1)*(p2[n2]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)*(p2[n4]-1)+(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1))
    ans += 2*(p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1)
    ans %= mod
print(ans)

Solution (Python):
from operator import itemgetter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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

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))

mod = 998244353
p2 = [1]*(N+1)
for i in range(N):
    p2[i+1] = p2[i]*2%mod

bit = BIT(N)

ans = 0

for i in range(N):
    y = xy[i][1]
    bit.add(y,1)
    n1 = i+1-bit.sum(y)
    n2 = i-n1
    n3 = N-y-1-n1
    n4 = N-i-1-n3
    ans += 1
    ans += (p2[n1]-1)+(p2[n2]-1)+(p2[n3]-1)+(p2[n4]-1)
    ans += (p2[n1]-1)*(p2[n2]-1)+(p2[n3]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)+(p2[n2]-1)*(p2[n4]-1)+2*(p2[n1]-1)*(p2[n4]-1)+2*(p2[n2]-1)*(p2[n3]-1)
    ans += 2*((p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)+(p2[n1]-1)*(p2[n2]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)*(p2[n4]-1)+(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1))
    ans += 2*(p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1)
    ans %= mod
print(ans)

Solution (Python):
from operator import itemgetter
import sys
input=sys.stdin.readline
mod=998244353

def bit_add(i):
    while i<=n:
        tree[i]+=1
        i+=i&(-i)
        
def bit_sum(i):
    s=0
    while i>0:
        s+=tree[i]
        i-=i&(-i)
    return s

n=int(input())
xy=[[i+1]+list(map(int,input().split())) for i in range(n)]
data=[[] for i in range(n+1)]
for i in [1,2]:
    xy.sort(key=itemgetter(i))
    for j in range(n):
        data[xy[j][0]].append(j+1)
    
data=sorted(data[1:])
lst=[]
for i1,i2 in data:
    lst.append(i2)

lsls=[1]*(n+1)
for i in range(1,n+1):
    lsls[i]=lsls[i-1]*2%mod
for i in range(n+1):
    lsls[i]-=1
    
s=pow(2,n,mod)-1
tree=[0]*(n+1)
ans=0
for i in range(n):
    y=lst[i]
    num=bit_sum(y)
    bit_add(y)
    a,b,c,d=i-num,num,y-1-num,n-y-i+num
    zzz=lsls[i]+lsls[n-i-1]+lsls[n-y]+lsls[y-1]
    yyy=lsls[a]+lsls[b]+lsls[c]+lsls[d]
    t=(zzz%mod-yyy%mod)%mod
    ans=(ans+s-t)%mod
print(ans)

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(set(x), key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)

    def add(self, idx, x):
        
        
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        
        
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        
        
        if w <= 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


MOD = 998244353
n = int(input())
x_list = []
y_list = []
for i in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
x_zipped, x_unzipped = compress_coordinate(x_list)
y_zipped, y_unzipped = compress_coordinate(y_list)

p = []
for i, (x, y) in enumerate(zip(x_list, y_list)):
    p.append((x_zipped[x], y_zipped[y], i))

info = [[0] * 5 for _ in range(n)]
p.sort(key=itemgetter(0))

bit1 = BIT1(n)
for m, (px, py, idx) in enumerate(p):
    bit1.add(py, 1)
    s_left = bit1.sum(py) - 1
    s_right = (m + 1) - s_left - 1
    info[idx][2] = s_right
    info[idx][3] = s_left

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


bit2 = BIT1(n)
for m, (px, py, idx) in enumerate(p):
    bit2.add(py, 1)
    s_left = bit2.sum(py) - 1
    s_right = (m + 1) - s_left - 1
    info[idx][1] = s_right
    info[idx][4] = s_left

ans = 0
for _, c1, c2, c3, c4 in info:
    c1 = pow(2, c1, MOD) - 1
    c2 = pow(2, c2, MOD) - 1
    c3 = pow(2, c3, MOD) - 1
    c4 = pow(2, c4, MOD) - 1
    ans += 1
    ans += c1 + c2 + c3 + c4
    ans += c1 * c3 * 2 + c2 * c4 * 2
    ans += c1 * c2 + c2 * c3 + c3 * c4 + c4 * c1
    ans += (c2 * c3 * c4 + c1 * c3 * c4 + c1 * c2 * c4 + c1 * c2 * c3) * 2
    ans += c1 * c2 * c3 * c4 * 2
    ans %= MOD


print(ans)

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(set(x), key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        
        
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        
        
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        
        
        if w <= 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


MOD = 998244353
n = int(input())
x_list = []
y_list = []
for i in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
x_zipped, x_unzipped = compress_coordinate(x_list)
y_zipped, y_unzipped = compress_coordinate(y_list)

p = []
for i, (x, y) in enumerate(zip(x_list, y_list)):
    p.append((x_zipped[x], y_zipped[y], i))

info = [[0] * 5 for _ in range(n)]
p.sort(key=itemgetter(0))

bit1 = BIT1(n)
for m, (px, py, idx) in enumerate(p):
    bit1.add(py, 1)
    s_left = bit1.sum(py) - 1
    s_right = (m + 1) - s_left - 1
    info[idx][2] = s_right
    info[idx][3] = s_left

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


bit2 = BIT1(n)
for m, (px, py, idx) in enumerate(p):
    bit2.add(py, 1)
    s_left = bit2.sum(py) - 1
    s_right = (m + 1) - s_left - 1
    info[idx][1] = s_right
    info[idx][4] = s_left

ans = 0
for _, c1, c2, c3, c4 in info:
    c1 = pow(2, c1, MOD) - 1
    c2 = pow(2, c2, MOD) - 1
    c3 = pow(2, c3, MOD) - 1
    c4 = pow(2, c4, MOD) - 1
    ans += 1
    ans += c1 + c2 + c3 + c4
    ans += c1 * c3 * 2 + c2 * c4 * 2
    ans += c1 * c2 + c2 * c3 + c3 * c4 + c4 * c1
    ans += (c2 * c3 * c4 + c1 * c3 * c4 + c1 * c2 * c4 + c1 * c2 * c3) * 2
    ans += c1 * c2 * c3 * c4 * 2
    ans %= MOD


print(ans)