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
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    MOD = 998244353

    N = int(readline())
    P = [list(map(int, readline().split())) for i in range(N)]

    P.sort()

    Y = [y for x, y in P]

    def compress(X):
        *XS, = set(X)
        XS.sort()
        return list(map({e: i for i, e in enumerate(XS)}.__getitem__, X))
    Y = compress(Y)

    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    pow2 = [1]*(N+1)
    r = 1
    for i in range(1, N+1):
        pow2[i] = r = r * 2 % MOD

    def gen(add, get, pow2):
        for i, y in enumerate(Y):
            v = get(y+1); add(y+1, 1)
            p1 = pow2[v]; p0 = pow2[y - v]
            q1 = pow2[i - v]; q0 = pow2[(N - y - 1) - (i - v)]
            yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % MOD
    write("%d\n" % ((sum(gen(add, get, pow2)) + N*pow2[N] - N) % MOD))
solve()

Solution (Python):
import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    MOD = 998244353

    N = int(readline())
    P = [list(map(int, readline().split())) for i in range(N)]

    P.sort()

    Y = [y for x, y in P]

    def compress(X):
        *XS, = set(X)
        XS.sort()
        return list(map({e: i for i, e in enumerate(XS)}.__getitem__, X))
    Y = compress(Y)

    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def gen(add, get):
        pow2 = [1]*N
        r = 1
        for i in range(1, N):
            pow2[i] = r = r * 2 % MOD

        for i, y in enumerate(Y):
            v1 = get(y+1); v0 = y - v1
            w1 = i - v1; w0 = (N - y - 1) - w1
            add(y+1, 1)
            p1 = pow2[v1]; p0 = pow2[v0]
            q1 = pow2[w1]; q0 = pow2[w0]
            yield (2 * (p1*p0 % MOD)*(q1*q0 % MOD) % MOD) - (1 - p0 - p1 - q0 - q1 + (p0 + q1) * (p1 + q0)) % MOD
    write("%d\n" % (sum(gen(add, get)) % MOD))
solve()

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

class BIT():
    def __init__(self,n):
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x):
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_to_i(self,i):
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s

n=int(input())
XY=[]
Y=[]
for _ in range(n):
    x,y=map(int,input().split())
    XY.append((x,y))
    Y.append(y)
Y.sort()
y_dict={y:i+1 for i,y in enumerate(Y)}
XY=[(x,y_dict[y]) for x,y in XY]
XY.sort()
bit=BIT(n)
pow_2=[1]
for _ in range(n):
    pow_2.append(pow_2[-1]*2%mod)
ans=0
for i,(x,y) in enumerate(XY):
    a=bit.sum_to_i(y)
    b=i-a
    c=y-a-1
    d=(n-i-1)-c
    bit.add(y,1)
    pa,pb,pc,pd=pow_2[a],pow_2[b],pow_2[c],pow_2[d]
    tmp=pow_2[n-1]
    tmp+=(pa-1)*(pd-1)*pb*pc%mod
    tmp+=(pb-1)*(pc-1)*pa*pd%mod
    tmp-=(pa-1)*(pb-1)*(pc-1)*(pd-1)%mod
    ans+=tmp
    ans%=mod
print(ans)

Solution (Python):
N = int(input())

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

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



from operator import itemgetter
def solve():
    p_list = XY[:]

    
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    
    p_list= sorted(p_list)

    
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    
    bit = Bit(N)
    ans = 0
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a = tmp
        b = i-tmp
        c = r-tmp-1
        d = (N-r+1)-(i-tmp)-1
        bit.add(r, 1)
        _a = power[a] - 1
        _b = power[b] - 1
        _c = power[c] - 1
        _d = power[d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()

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

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD

ans += pow2[n-1] * n % MOD
print(ans % MOD)

Solution (Python):
from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]
xy.sort()

ylist = [y for _, y in xy]
ylist.sort()
for i in range(N) :
    xy[i] = [i, bisect_left(ylist, xy[i][1])]

MOD = 998244353

def bit_sum(i) :
    s = 0
    while i > 0 :
        s += bit[i]
        i -= i & -i
    return s

def bit_add(i, x) :
    while i <= N :
        bit[i] += x
        i += i & -i

lu = [0] * N
ld = [0] * N
ru = [0] * N
rd = [0] * N

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

bit = [0] * (N + 1)
for i, (x, y) in enumerate(xy) :
    ld[i] = bit_sum(y+1)
    lu[i] = i - ld[i]
    bit_add(y+1, 1)

bit = [0] * (N + 1)
for i, (x, y) in enumerate(xy[::-1]) :
    rd[N-i-1] = bit_sum(y+1)
    ru[N-i-1] = i - rd[N-i-1]
    bit_add(y+1, 1)

ret = 0
for i in range(N) :
    ret += (power[lu[i]]-1)*power[ld[i]]*power[ru[i]]*(power[rd[i]]-1)
    ret += power[lu[i]]*(power[ld[i]]-1)*(power[ru[i]]-1)*power[rd[i]]
    ret -= (power[lu[i]]-1)*(power[ld[i]]-1)*(power[ru[i]]-1)*(power[rd[i]]-1)
    ret += power[lu[i]] * power[ld[i]] * power[ru[i]] * power[rd[i]]
    ret %= MOD
    
print(ret)

Solution (Python):
N = int(input())
XY = [[int(x) for x in input().split()] for i in range(N)]
mod = 998244353
XY.sort() 
X, Y = zip(*XY)
Y_rank = {x:i for i, x in enumerate(sorted(Y), 1)}
BIT = [0] * (N+1)

def append_BIT(x):
    while x <= N:
        BIT[x] += 1
        x += x & (-x)

def sum_BIT(x):
    ret = 0
    while x:
        ret += BIT[x]
        x &= (x-1)
    return ret

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

ret = 0 
for i in range(N):
    y = Y_rank[Y[i]]
    L = i
    R = N-i-1
    D = y-1
    U = N-D-1
    LD = sum_BIT(y)
    append_BIT(y)
    LU = L - LD
    RU = U - LU
    RD = D - LD
    
    ret += (pow2[N]-1 - pow2[L] - pow2[R] - pow2[U] - pow2[D] + pow2[LD] + pow2[LU] + pow2[RU] + pow2[RD])
    
ret %= mod
print(ret)

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

N=int(input())
POINT=[list(map(int,input().split())) for i in range(N)]
mod=998244353

compression_dict_x={a: ind for ind, a in enumerate(sorted(set([p[0] for p in POINT])))}
POINT=[[compression_dict_x[x]+1,y] for x,y in POINT]
P_Y=sorted(POINT,key=lambda x:x[1])



LEN=len(compression_dict_x)

BIT=[0]*(LEN+1)

def update(v,w):
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v))

def getvalue(v):
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v))
    return ANS

ANS= 4*N+(pow(2,N,mod)-1)*(N-4)%mod

for i in range(N):
    x,y=P_Y[i]
    left=getvalue(x)
    ANS=(ANS+pow(2,left,mod)+pow(2,i-left,mod)-2)%mod
    update(x,1)

P_Y.reverse()
BIT=[0]*(LEN+1)

for i in range(N):
    x,y=P_Y[i]
    left=getvalue(x)
    ANS=(ANS+pow(2,left,mod)+pow(2,i-left,mod)-2)%mod
    update(x,1)

print(ANS)

Solution (Python):

import sys
input = sys.stdin.readline
 

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

 
N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
 
point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i
 
mod = 998244353
 
ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod
 
pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod
 
point.sort(lambda x: x[0])
 
bit = BIT([0]*len(point))
 
 
for i,(x,y) in enumerate(point):
    if y > 0:
        ld = bit.sum(y-1)
        
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    bit.add(y,1)
 
print(ans)

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

N=int(input())
POINT=[list(map(int,input().split())) for i in range(N)]
mod=998244353

PX=[p[0] for p in POINT]
PY=[p[1] for p in POINT]

compression_dict_x={a: ind for ind, a in enumerate(sorted(set(PX)))}
compression_dict_y={a: ind for ind, a in enumerate(sorted(set(PY)))}

for i in range(N):
    POINT[i]=[compression_dict_x[POINT[i][0]]+1,compression_dict_y[POINT[i][1]]+1]


P_Y=sorted(POINT,key=lambda x:x[1])



LEN=len(compression_dict_x)

BIT=[0]*(LEN+1)

def update(v,w):
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v))

def getvalue(v):
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v))
    return ANS


ALL = pow(2,N,mod)-1

ANS= ALL*N%mod

for i in range(N):
    ANS = (ANS - (pow(2,i,mod) -1)*4)%mod

for i in range(N):
    x,y=P_Y[i]
    up=getvalue(x)

    ANS=(ANS+pow(2,up,mod)+pow(2,i-up,mod)-2)%mod

    update(x,1)

P_Y2=P_Y[::-1]
BIT=[0]*(LEN+1)

for i in range(N):
    x,y=P_Y2[i]
    down=getvalue(x)

    ANS=(ANS+pow(2,down,mod)+pow(2,i-down,mod)-2)%mod

    update(x,1)


print(ANS)

Solution (Python):

import sys
input = sys.stdin.readline


class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

N = int(input())
point = [list(map(int,input().split())) for i in range(N)]

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(point), lambda a,b:a+b, 0)


for i,(x,y) in enumerate(point):
    if point[i][1] > 0:
        ld = ST.get(0,y-1)
        
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)

Solution (Python):

import sys
import bisect

MOD = 998244353  

class BitIndexedTree(object):
    def __init__(self, N):
        self.V = [0] * N
        self.N = N
    
    def __getitem__(self, key):
        return self.sum(key, key+1)
    
    def __setitem__(self, key, value):
        diff = value - self[key]
        self.add(diff, key)

    def add(self, w, a):
        if w == 0:
            return
        x = a
        while x <= self.N:
            self.V[x-1] += w
            x += x & -x
    
    def sum(self, start=0, end=0):
        if end <= start:
            return 0
        if start > 0:
            return self.sum(0, end) - self.sum(0, start)
        x = end
        ret = 0
        while x > 0:
            ret += self.V[x-1]
            x -= x & -x
        return ret


def solve(N: int, P: "List[tuple]"):
    res = 0
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % MOD

    P.sort(key=lambda x: x[1])
    for i, p in enumerate(P):
        p[1] = i
    
    P.sort()
    for i, p in enumerate(P):
        p[0] = i
    left = BitIndexedTree(N)
    right = BitIndexedTree(N)

    ll = [0] * N
    lg = [0] * N
    gl = [0] * N
    gg = [0] * N

    for i, p in enumerate(P):
        ll[i] = left.sum(0, p[1])
        lg[i] = i-ll[i]
        left.add(1, p[1]+1)

    for i, p in enumerate(P[::-1]):
        gl[-1-i] = right.sum(0, p[1])
        gg[-1-i] = i-gl[-1-i]
        right.add(1, p[1]+1)

    for a1, a2, a3, a4 in zip(gg, lg, ll, gl):
        b1 = power[a1]
        b2 = power[a2]
        b3 = power[a3]
        b4 = power[a4]

        res += (b1 - 1) * (b3 - 1) * b2 * b4
        res += (b2 - 1) * (b4 - 1) * b1 * b3

        res -= (b1 - 1) * (b2 - 1) * (b3 - 1) * (b4 - 1)

        res += power[N-1]

        res %= MOD
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = [()] * (N)  
    for i in range(N):
        x = int(next(tokens))
        y = int(next(tokens))
        P[i] = [x, y]
    solve(N, P)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import bisect

MOD = 998244353  

class BitIndexedTree(object):
    def __init__(self, N):
        self.V = [0] * N
        self.N = N
    
    def __getitem__(self, key):
        return self.sum(key, key+1)
    
    def __setitem__(self, key, value):
        diff = value - self[key]
        self.add(diff, key)

    def add(self, w, a):
        if w == 0:
            return
        x = a
        while x <= self.N:
            self.V[x-1] += w
            x += x & -x
    
    def sum(self, start=0, end=0):
        if end <= start:
            return 0
        if start > 0:
            return self.sum(0, end) - self.sum(0, start)
        x = end
        ret = 0
        while x > 0:
            ret += self.V[x-1]
            x -= x & -x
        return ret


def solve(N: int, P: "List[tuple]"):
    res = 0
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % MOD

    P.sort(key=lambda x: x[1])
    for i, p in enumerate(P):
        p[1] = i
    
    P.sort()
    for i, p in enumerate(P):
        p[0] = i
    left = BitIndexedTree(N)
    right = BitIndexedTree(N)

    ll = [0] * N
    lg = [0] * N
    gl = [0] * N
    gg = [0] * N

    for i, p in enumerate(P):
        ll[i] = left.sum(0, p[1])
        lg[i] = i-ll[i]
        left.add(1, p[1]+1)

    for i, p in enumerate(P[::-1]):
        gl[-1-i] = right.sum(0, p[1])
        gg[-1-i] = i-gl[-1-i]
        right.add(1, p[1]+1)

    for a1, a2, a3, a4 in zip(gg, lg, ll, gl):
        b1 = power[a1]
        b2 = power[a2]
        b3 = power[a3]
        b4 = power[a4]

        res += (b1 - 1) * (b3 - 1) * b2 * b4
        res += (b2 - 1) * (b4 - 1) * b1 * b3

        res -= (b1 - 1) * (b2 - 1) * (b3 - 1) * (b4 - 1)

        res += b1 * b2 * b3 * b4

        res %= MOD
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = [()] * (N)  
    for i in range(N):
        x = int(next(tokens))
        y = int(next(tokens))
        P[i] = [x, y]
    solve(N, P)

if __name__ == '__main__':
    main()

Solution (Python):
def f_encolsed_points(MOD=998244353):
    
    import sys
    input = sys.stdin.readline

    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

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

        def sum(self, index):
            """tree[1]からtree[index]までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value=1):
            """tree[index]にvalueを加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    N = int(input())
    Pos = [[int(i) for i in input().split()] for j in range(N)]

    Pos.sort()  
    _, pos_y = zip(*Pos)
    y_comp = {y: i for i, y in enumerate(sorted(pos_y), 1)}  

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

    ans = 0
    tree = BIT(N)
    
    for left, (_x, _y) in enumerate(Pos):
        y = y_comp[_y]

        
        right = N - 1 - left
        down = y - 1
        up = N - 1 - down

        lower_left = tree.sum(y)
        tree.add(y, 1)
        upper_left = left - lower_left
        lower_right = down - lower_left
        upper_right = right - lower_right

        
        count = (pow_2[N]
                 - (pow_2[up] + pow_2[down] + pow_2[left] + pow_2[right])
                 + (pow_2[upper_left] + pow_2[lower_left] + pow_2[upper_right] + pow_2[lower_right])
                 - 1)
        ans += count
        ans %= MOD
    return ans

print(f_encolsed_points())

Solution (Python):


"""
Binary indexed tree
0-indexed, 関数は閉区間
0からの区間加算、1点更新
"""
class BIT: 
    def __init__(self, n):
        self.tree = [0]*(n+1)
        self.tree[0] = None

    def sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def range(self,l,r): 
        return sum(r) - sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= n:
            self.tree[i] += x
            i += i & -i
        
    
    


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
xyi = [[int(i) for i in readline().split()]+[j] for j in range(n)]









ABi = [0]*n
CDi = [0]*n

MOD = 998244353

sxyi = sorted(xyi, key = lambda x: x[1])
zaatu = [0]*n
for j in range(n): zaatu[sxyi[j][2]] = j
for j, (x,y,i) in enumerate(sxyi):
    ABi[i] = n-j-1
    CDi[i] = j

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


xyi.sort()


bit = BIT(n)

ans = n*(pow2[n]-1)%MOD
for j, (x,y,i) in enumerate(xyi):
    AB = ABi[i]
    CD = CDi[i]
    BC = j
    AD = n-j-1
    c = bit.sum(zaatu[i])
    C = c
    B = j-c

    ans -= pow2[AB]-1 + pow2[CD]-1 
    ans -= pow2[BC]-1 + pow2[AD]-1
    ans += pow2[C]-1 + pow2[CD-C]-1 + pow2[B]-1 + pow2[AB-B]-1

    bit.add(zaatu[i],1)
        

        


print(ans%MOD)

Solution (Python):


"""
Binary indexed tree
0-indexed, 関数は閉区間
0からの区間加算、1点更新
"""
class BIT: 
    def __init__(self, n):
        self.tree = [0]*(n+1)
        self.tree[0] = None

    def sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def range(self,l,r): 
        return sum(r) - sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= n:
            self.tree[i] += x
            i += i & -i
        
    
    




import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
xyi = [[int(i) for i in readline().split()]+[j] for j in range(n)]





dame_x = [0]*n
dame_y = [0]*n
dame_xy = [0]*n

MOD = 998244353

sxyi = sorted(xyi, key = lambda x: x[1]) 
modosu = [i for x,y,i in sxyi]
zaatu = [0]*n
for j,zj in enumerate(modosu):
    zaatu[zj] = j

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

for j, (x,y,i) in enumerate(sxyi):
    dame_y[i] = pow2[j]-1 + pow2[n-j-1]-1

xyi.sort()


bit = BIT(n)
for j, (x,y,i) in enumerate(xyi):
    dame_x[i] = pow2[j] -1 + pow2[n-j-1]-1
    c = bit.sum(zaatu[i])
    dame_xy[i] += pow2[c]-1 + pow2[j-c]-1
    bit.add(zaatu[i],1)
        
bit = BIT(n)
for j, (x,y,i) in enumerate(reversed(xyi)):
    c = bit.sum(zaatu[i])
    dame_xy[i] += pow2[c]-1 + pow2[j-c]-1
    bit.add(zaatu[i],1)
        
        


ans = n*(pow2[n]-1)%MOD
for dx,dy,dxy in zip(dame_x,dame_y,dame_xy):
    ans += - dx - dy + dxy


print(ans%MOD)

Solution (Python):


"""
Binary indexed tree
0-indexed, 関数は閉区間
0からの区間加算、1点更新
"""
class BIT: 
    def __init__(self, n):
        self.tree = [0]*(n+1)
        self.tree[0] = None

    def sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def range(self,l,r): 
        return sum(r) - sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= n:
            self.tree[i] += x
            i += i & -i
        
    
    




import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
xyi = []
for i in range(n):
    a = [int(i) for i in readline().split()]
    xyi.append(a+[i])

dame_x = [0]*n
dame_y = [0]*n
dame_xy = [0]*n

MOD = 998244353

sxyi = sorted(xyi, key = lambda x: x[1]) 
modosu = [i for x,y,i in sxyi]
zaatu = [0]*n
for j,zj in enumerate(modosu):
    zaatu[zj] = j

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

for j, (x,y,i) in enumerate(sxyi):
    dame_y[i] = pow2[j]-1 + pow2[n-j-1]-1

xyi.sort()


bit = BIT(n)
for j, (x,y,i) in enumerate(xyi):
    dame_x[i] = pow2[j] -1 + pow2[n-j-1]-1
    c = bit.sum(zaatu[i])
    dame_xy[i] += pow2[c]-1 + pow2[j-c]-1
    bit.add(zaatu[i],1)
        
bit = BIT(n)
for j, (x,y,i) in enumerate(reversed(xyi)):
    c = bit.sum(zaatu[i])
    dame_xy[i] += pow2[c]-1 + pow2[j-c]-1
    bit.add(zaatu[i],1)
        
        


ans = n*(pow2[n]-1)%MOD
for dx,dy,dxy in zip(dame_x,dame_y,dame_xy):
    ans += - dx - dy + dxy


print(ans%MOD)

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

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

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

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1
    r2 = N-xy[i][1]-l2-1
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-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
        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())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

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

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

print(ans)

Solution (Python):
class BIT:
  ini = 0
  def __init__(self, num):
    self.N = 1
    while self.N <= num:
      self.N *= 2
    self.T = [self.ini] * self.N
  def do(self, l, r):
    
    return l + r
  def set(self, L):
    for i in range(len(L)):
      self.update(i, L[i])
  def update(self, x):
    k = x + 1
    self.T[k - 1] += 1
    k += k & -k
    while k <= N:
      self.T[k - 1] += 1
      k += k & -k
  def getV(self, x):
    ans = self.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += self.T[x - 1]
      x -= x & -x
    return ans

import sys
input = sys.stdin.readline
N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
MOD = 998244353

xy.sort(key = lambda x:x[1])
R = {}
for i in range(N):
  R[xy[i][1]] = i
xy.sort()

LU = [0] * N
LD = [0] * N
RU = [0] * N
RD = [0] * N

Sl = BIT(N)
for i in range(N):
  t = Sl.getV(R[xy[i][1]])
  LU[i] = i - t
  LD[i] = t
  Sl.update(R[xy[i][1]])

Sr = BIT(N)
for i in range(N-1 , -1 , -1):
  t = Sr.getV(R[xy[i][1]])
  RU[i] = (N - 1 - i) - t
  RD[i] = t
  Sr.update(R[xy[i][1]])

ans = 0
PL = [1]
for i in range(N + 1):
  PL.append(PL[-1] * 2 % MOD)

def na(x):
  return PL[x] - 1

for i in range(N):
  t = PL[N - 1]
  t = (t + na(LU[i]) * na(RD[i])) % MOD
  t = (t + na(LD[i]) * na(RU[i])) % MOD
  t = (t + na(LU[i]) * na(LD[i]) * na(RU[i])) % MOD
  t = (t + na(LU[i]) * na(LD[i]) * na(RD[i])) % MOD
  t = (t + na(LU[i]) * na(RD[i]) * na(RU[i])) % MOD
  t = (t + na(LD[i]) * na(RD[i]) * na(RU[i])) % MOD
  t = (t + na(LU[i]) * na(LD[i]) * na(RD[i]) * na(RU[i])) % MOD
  ans = (ans + t) % 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
        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 = 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_nor_list = [xy[1] for xy in XY]

sg_left = Bit(N)
sg_right = Bit(N)

left_lower = [0] * N
left_upper = [0] * N
right_lower = [0] * N
right_upper = [0] * N

for i in range(N):
    c = y_nor_list[i] + 1
    left_lower[i] = sg_left.sum(c)
    left_upper[i] = i - left_lower[i]
    sg_left.add(c, 1)

for i in range(N-1, -1, -1):
    c = y_nor_list[i] + 1
    right_lower[i] = sg_right.sum(c)
    right_upper[i] = N - 1 - i - right_lower[i]
    sg_right.add(c, 1)






LARGE = 998244353

pow2m1 = [0] * (N + 1)
for i in range(1, N + 1):
    pow2m1[i] = (2 * pow2m1[i - 1] + 1) % LARGE

res = 0
for i in range(N):
    r = pow2m1[N]
    r -= pow2m1[left_lower[i] + left_upper[i]]
    r -= pow2m1[right_lower[i] + right_upper[i]]
    r -= pow2m1[left_lower[i] + right_lower[i]]
    r -= pow2m1[left_upper[i] + right_upper[i]]
    r += pow2m1[left_lower[i]]
    r += pow2m1[left_upper[i]]
    r += pow2m1[right_lower[i]]
    r += pow2m1[right_upper[i]]
    res += r

print(res % LARGE)