diff --git a/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java b/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java
index cbb66dc..9149842 100644
--- a/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java
+++ b/services/accessibility/java/com/android/server/accessibility/AccessibilityManagerService.java
@@ -2647,10 +2647,13 @@
                 userState.mComponentNameToServiceMap;
         boolean isUnlockingOrUnlocked = mUmi.isUserUnlockingOrUnlocked(userState.mUserId);
 
+        // Store the list of installed services.
+        mTempComponentNameSet.clear();
         for (int i = 0, count = userState.mInstalledServices.size(); i < count; i++) {
             AccessibilityServiceInfo installedService = userState.mInstalledServices.get(i);
             ComponentName componentName = ComponentName.unflattenFromString(
                     installedService.getId());
+            mTempComponentNameSet.add(componentName);
 
             AccessibilityServiceConnection service = componentNameToServiceMap.get(componentName);
 
@@ -2710,6 +2713,25 @@
             audioManager.setAccessibilityServiceUids(mTempIntArray);
         }
         mActivityTaskManagerService.setAccessibilityServiceUids(mTempIntArray);
+
+        // If any services have been removed, remove them from the enabled list and the touch
+        // exploration granted list.
+        boolean anyServiceRemoved =
+                userState.mEnabledServices.removeIf((comp) -> !mTempComponentNameSet.contains(comp))
+                        || userState.mTouchExplorationGrantedServices.removeIf(
+                                (comp) -> !mTempComponentNameSet.contains(comp));
+        if (anyServiceRemoved) {
+            // Update the enabled services setting.
+            persistComponentNamesToSettingLocked(
+                    Settings.Secure.ENABLED_ACCESSIBILITY_SERVICES,
+                    userState.mEnabledServices,
+                    userState.mUserId);
+            // Update the touch exploration granted services setting.
+            persistComponentNamesToSettingLocked(
+                    Settings.Secure.TOUCH_EXPLORATION_GRANTED_ACCESSIBILITY_SERVICES,
+                    userState.mTouchExplorationGrantedServices,
+                    userState.mUserId);
+        }
         updateAccessibilityEnabledSettingLocked(userState);
     }